Hledání minimálního počtu uzlů ve stromě (C++) – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Hledání minimálního počtu uzlů ve stromě (C++) – C / C++ – Fórum – Programujte.comHledání minimálního počtu uzlů ve stromě (C++) – C / C++ – Fórum – Programujte.com

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

Fantom40
Duch
23. 6. 2017   #1
-
0
-

Dobrý den,potřeboval bych poradit s program pro nalezení minimálního počtu uzlů ve stromě. Program "hrubou" silou mám, ale ještě mi chybí program pomocí dynamického programování. Můžete mi prosím poradit?Program hrubou silou: (Visual Studio 2013)

#include "stdafx.h"
#include <iostream>
#include <algorithm> 
using namespace std;
int opakovani = 0;


int image[4][4] = {
    { 1, 1 ,1 ,1 },
    { 0,0, 0 ,1 },
    { 0, 0, 0 ,1 },
    { 1, 1 ,1 ,1 },
    };

int deleni(int x1, int x2, int y1, int y2);

int main()
{
    int vysl = deleni(0,3, 0,3);
    cout <<"Nejmensi pocet uzlu je: "<< vysl << endl;
    cout << opakovani;
    cin.get();
    cin.get();
    return 0;
}

int deleni(int x1, int x2, int y1, int y2) {

    bool black = false;

    bool white = false;

    for (int i = x1; i <= x2; i++) {

        for (int j = y1; j <= y2; j++) {
            
             
            
            if (image[i][j] == 0)
            {
                    
                white = true;
            }
            if (image[i][j] == 1)
            {
                
                black = true;
            }

        }

    }
    
    
    if (!(black & white)) { opakovani++; return 1; }

    // TADY BYCH DAL TEST, JESTLI VÝSLEDEK S PARAMETRY int x1, int x2, int y1, int y2 UŽ JE V SEZNAMU, POKUD ANO, TAK HO ROVNOU VRÁTÍM

    int vysledek = 2 * (x2 - x1 + 1) * (y2 - y1 + 1) - 1;

    for (int i = y1; i < y2; i++) {
        
        vysledek = min(vysledek, deleni(x1, x2, y1, i) + deleni(x1, x2, i + 1, y2) + 1);
    }

    for (int i = x1; i < x2; i++) {
        vysledek = min(vysledek, deleni(x1, i, y1, y2) + deleni(i + 1, x2, x1, y2) + 1);
    }
    
    
    // TADY BYCH ULOŽIL DO SEZNAMU REŠENÍ S PARAMETRY int x1, int x2, int y1, int y2
    opakovani++;    
    return vysledek;
}

Nahlásit jako SPAM
IP: 84.19.89.–
gna
~ Anonymní uživatel
930 příspěvků
23. 6. 2017   #2
-
0
-

Nechce se mi nad tím přemýšlet, ale myslím si, že do toho prvního cyklu pro dělění podle Y můžeš rovnou hodit ještě dělení podle X a budeš to mít bez opakování.

Jinak na to ukládání předchozích výsledků je pohodlné použít std::map (ale myslím si, že to teda nepotřebuješ).

Nahlásit jako SPAM
IP: 213.211.51.–
gna
~ Anonymní uživatel
930 příspěvků
23. 6. 2017   #3
-
0
-

Tak ne, to dělení uvnitř je blbost.

Nahlásit jako SPAM
IP: 213.211.51.–
Fantom40
Duch
24. 6. 2017   #4
-
0
-

#3 gna
A Nějaká jiná rada by nebyla?

Nahlásit jako SPAM
IP: 84.19.89.–
gna
~ Anonymní uživatel
930 příspěvků
24. 6. 2017   #5
-
0
-

A s čím chceš poradit? Máš to správně, jen doplň tu optimalizaci.

Nahlásit jako SPAM
IP: 213.211.51.–
Fantom40
Duch
24. 6. 2017   #6
-
0
-

#5 gna
To mi právě nejde, nějak se přes to nemůžu dostat.

Nahlásit jako SPAM
IP: 84.19.89.–
Doomista+1
Stálý člen
24. 6. 2017   #7
-
0
-

Ideální způsob by bylo použít std::unordered_map, ale pro ten by sis musel naimplementovat vlastní hashovací funkci, což není úplně sranda. Je tu ale i naivní přístup, který v tomto případě bude stačit, v praxi by byl paměťově dost drahý.

V první řadě: 2D pole je pomalejší než 1D pole. Pokud chci mít 2D pole s S sloupci a R řádky, stačí mi 1D pole o velikosti S x R. Pro přístup k položce na souřadnicích x,y mi pak stačí vzorec y * S + x. Toho bys mohl využít. Možných výsledků dělení je 16 x 16. Mohl by sis udělat 2D pole 16 x 16, naplněné hodnotami -1, které by znamenaly, že tam není nic vypočítaného. Pro přístup k výsledku dělení s parametry x1, y1, x2, y2 bys pak použil formuli výsledek[y1 * 4 + x1][y2 * 4 + x2]. Pokud by tam byla -1, musel by sis to spočítat, pokud by tam bylo cokoliv jiného, vrátil bys to. Mohl by sis dokonce zafajnšmekřit a implementovat to 1D polem (odvození výpočtu indexu nechám na tobě).

Existuje i třetí cesta střední obtížnosti a střední výkonosti - zjednodušená implementace řídkého vektoru. Velice zjednodušeně bys měl nafukovací pole, do kterého bys pro každý spočítaný výsledek vložil ntici x1,y1,x2,y2 a příslušný výsledek. Při hledání výsledku bys ale musel projít celé to nafukovací pole a hledat, zda v něm máš příslušný výsledek (stále je to ale výkonnější než to, co děláš teď). V jistém smyslu slova pro toto jde využít i std::map (která to prohledávání udělá za tebe), ale mám podezření, že bys do ní musel narvat porovnávací funkci, což není tak težké, jako ta hashovací, ale nevím, jestli na to stačí tvé zkušenosti.

Snad jsem to napsal dostatečně srozumitelně. Mmch pár připomínek ke kódu, který máš: podmínky v těch dvou zanořených forech nemusí být if a if, ale if a else if, neboť ty děláš buď a nebo. Postřeh 2: if (!black & white)) ti sice funguje, ale pochybuji, žes to tak napsal záměrně. Je rozdíl mezi & a &&. To první provede binární součin a podmínka něco a něco je realizována operátorem &&. Při importu knihovny ciso646 můžeš používat i podstatně výmluvnější klíčové slovo 'and' (a taky or a not).
 

Nahlásit jako SPAM
IP: 2a00:1028:83a0:33ea:8d58:...–
Na vše stačí iostream...
gna
~ Anonymní uživatel
930 příspěvků
24. 6. 2017   #8
-
+1
-
Zajímavé

   

#include <map>
#include <sstream>
...
// treba string -> int
map<string, int> cache;
...
int deleni(int x1, int x2, int y1, int y2) {
	...
	stringstream ss;
	ss << x1 << "," << x2 << "," << y1 << "," << y2;
	string key = ss.str();

	// pokud klic v mape neni, tak se timhle ctenim i vytvori
	// v nasem pripade to nevadi, protoze ho tam stejne budeme vkladat
	vysledek = cache[key];
	
	// pokud byl klic vytvoren, tak s vychozi hodnotu
	// v nasem pripade intu tedy 0, kterou tam jinak nevkladame
	// takze nenulova hodnota je drive explicitne vlozena hodnota
	if (vysledek)
		return vysledek;

	vysledek = vypocet...

	cache[key] = vysledek;
Nahlásit jako SPAM
IP: 213.211.51.–
Doomista+1
Stálý člen
24. 6. 2017   #9
-
0
-

#8 gna
Velice elegantní řešení. Není nejrychlejší, ale zato je nejjednodušší

Nahlásit jako SPAM
IP: 2a00:1028:83a0:33ea:8d58:...–
Na vše stačí iostream...
Fantom40
Duch
28. 6. 2017   #10
-
0
-

#8 gna
Děkuji mnohokrát.

Nahlásit jako SPAM
IP: 84.19.89.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 51 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032019 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý