anzahl for schleifen dynamisch

Bashar

Nein, ist es nicht, aber vielleicht ist dein Problem rekursiv einfacher zu lösen. Was hast du denn vor?

Ich könnte mir als Grund nur Folgendes denken:
Wenn man einen iterativen Bruteforcealgorithmus schreiben möchte

vector<char>wort;
wort.push_back('a');
wort.push_back('b');
wort.push_back('c');

//bruteforce für 3 stellen
for(unsigned int a=0;a!=wort.size();++a)
    for(unsigned int b=0;b!=wort.size();++b)
        for(unsigned int c=0;c!=wort.size();++c)
            cout<<wort[a]<<wort[b]<<wort[c]<<endl;

Wenn man die zahl der For-Schleifen dynamisch ändern könnte, könnte man so sehr leicht einen iterativen bruteforcealgo schreiben...

berniebutt

Meinst Deu mit dynamisch 'laufzeitabhängig'? Dann nimm statt for-Schleifen einfach while-Schleifen.

Kóyaánasqatsi

So verschwand Mogli in den tiefen Weiten der tropischen Regenwälder...

pumuckl

Einfache Version:

std::vector<int> limits;
limits.push_back(6); //erste schleife geht bis 5
/* ein paar weitere limits */
std::vector<int> counters;
counters.resize(limits.size());

typedef std::vector<int>::iterator iter_t;
void nested_for(iter_t limit, iter_t counter)
{
  iter_t next = limit; ++next; //next zeigt auf das limit der nächsten schleife
  for (*counter = 0; *counter < *limit; ++(*counter))
  {
    if(next != limits.end())
    {
      nested_for(next, ++counter); //nächstinnere Schleife aufrufen
    }
    else //innerste Schleife
    {
      cout << counters[0] << counters[1] << counters[2] << /* ... */ << endl;
    }
  }
}

//jetzt einfach aufrufen:
nested_for(limits.begin(), counters.begin());

Das ist jetzt nur mal so hingeferkelt die Grundidee - das kann man natürlich noch n ganzes Stück generischer ausarbeiten, ich denk aber man erkennts

^ne keine sorge bin nicht verschwunden,

also was ich machen will ist eigetnlich ganz simpel

also ich will vorgeben wieviele zahlen es geben soll in einer reihe , alle zusammen dürfen müssen immer eine bestimmte summe ergeben.

ich mach das mal für drei zahlen und die summe muss zb 12 sein.
davon alle möglichen kombinationen

4 4 4 = 12

3 4 5 = 12

2 4 6 = 12

1 4 7 = 12

1 3 6 = 12

usw.

so mit drei statischen for schleifen kriege ich das hin.

wenn ich aber zb 10 zahlen in einer reihe haben möchte müsste ich ja 10 for schleifen schreiben.

ich guck mir mal die antworten an vielleicht kann ich dass ja gebrauchen. bin aber erst wieder in 2 stunden am rechner

vielen dank bis hier hin schonmal

hoffe mein problem ist jetzt verständlich

gruss mogli 3

guess schrieb:

Ich könnte mir als Grund nur Folgendes denken:
Wenn man einen iterativen Bruteforcealgorithmus schreiben möchte
vector<char>wort;
wort.push_back('a');
wort.push_back('b');
wort.push_back('c');

//bruteforce für 3 stellen
for(unsigned int a=0;a!=wort.size();++a)
    for(unsigned int b=0;b!=wort.size();++b)
        for(unsigned int c=0;c!=wort.size();++c)
            cout<<wort[a]<<wort[b]<<wort[c]<<endl;
Wenn man die zahl der For-Schleifen dynamisch ändern könnte, könnte man so sehr leicht einen iterativen bruteforcealgo schreiben...

verstehe ich nicht ganz, wie kann man denn die anzhal dynamisch ändern? du schreibst wenn man sie ändern könnte, das wollte ich ja auch.

pumuckl

Rekursive Lösung:

typedef std::vector<unsigned int> reihen_t; //für einen Satz Summanden
typedef std::vector<reihen_t> allereihen_t;

void bauereihen(std::size_t n, //so viele Reihenelemente sollen noch kommen
                unsigned int restsumme, //so viel fehlt noch zur Summe
                allereihen_t& allereihen, //hier werden alle Reihen abgespeichert
                reihen_t& bisherigereihe) //hier werden die Reihenelemente angehängt
{
   if (n == 1) //letztes Element
   {
     bisherigereihe.push_back(restsumme);
     allereihen.push_back(bisherigereihe);
     bisherigereihe.pop_back();
   }
   else 
   {
     //Der nächste Summand muss immer größer als der Vorgänger sein,
     //d.h. er ist minimal so groß wie das letzte Element der bisherigen Reihe
     //(oder 1), maximal restsumme/n
     unsigned int mins = (bisherigereihe.empty()) ? 1 : *(bisherigereihe.rbegin());
     unsigned int maxs = restsumme/n;
     for (unsigned int s = mins; s <= maxs; ++s)
     {
       bisherigereihe.push_back(s);
       bauereihen(n-1, restsumme-s, allereihen, bisherigereihe); //REKURSION
       bisherigereihe.pop_back();
     }
   }
}

int main()
{
  unsigned int summe = 12;
  std::size_t n = 3;
  reihen_t r;
  allereihen_t a;

  //Aufruf:
  bauereihen(n, summe, a, r);

  for (allereihen_t::iterator ita = a.begin(); ita != a.end() ++ita)
  {
    for (reihen_t::iterator itr = (*ita).begin(); itr != (*ita).end(); ++itr)
    {
      if (itr != (*ita).begin()) std::cout << "+ ";
      std::cout << *itr << " ";
    }
    std::cout << "= " << summe << std::endl << std::endl;
  }
}

Das Ganze jetzt in eine iterative Lösung umzubauen sei den Threadersteller zur Übung überlassen - Tip: es braucht nur 2 geschachtelte for-schleifen

Firefighter

Ich bin mir nicht ganz sicher aber ist da ein kleiner Fehler drinne pumuckl? Wo kommt denn bei dir das hier her:

typedef std::vector<Reihe> allereihen_t;//Wo wird 'Reihe' deklariert?

Hab ich wirklich wat übersehen?

pumuckl

sed 's/Reihe/reihen_t/'

Sorry, habs korrigiert

pumuckl schrieb:

Rekursive Lösung:

typedef std::vector<unsigned int> reihen_t; //für einen Satz Summanden
typedef std::vector<reihen_t> allereihen_t;

void bauereihen(std::size_t n, //so viele Reihenelemente sollen noch kommen
                unsigned int restsumme, //so viel fehlt noch zur Summe
                allereihen_t& allereihen, //hier werden alle Reihen abgespeichert
                reihen_t& bisherigereihe) //hier werden die Reihenelemente angehängt
{
   if (n == 1) //letztes Element
   {
     bisherigereihe.push_back(restsumme);
     allereihen.push_back(bisherigereihe);
     bisherigereihe.pop_back();
   }
   else 
   {
     //Der nächste Summand muss immer größer als der Vorgänger sein,
     //d.h. er ist minimal so groß wie das letzte Element der bisherigen Reihe
     //(oder 1), maximal restsumme/n
     unsigned int mins = (bisherigereihe.empty()) ? 1 : *(bisherigereihe.rbegin());
     unsigned int maxs = restsumme/n;
     for (unsigned int s = mins; s <= maxs; ++s)
     {
       bisherigereihe.push_back(s);
       bauereihen(n-1, restsumme-s, allereihen, bisherigereihe); //REKURSION
       bisherigereihe.pop_back();
     }
   }
}

int main()
{
  unsigned int summe = 12;
  std::size_t n = 3;
  reihen_t r;
  allereihen_t a;

  //Aufruf:
  bauereihen(n, summe, a, r);

  for (allereihen_t::iterator ita = a.begin(); ita != a.end() ++ita)
  {
    for (reihen_t::iterator itr = (*ita).begin(); itr != (*ita).end(); ++itr)
    {
      if (itr != (*ita).begin()) std::cout << "+ ";
      std::cout << *itr << " ";
    }
    std::cout << "= " << summe << std::endl << std::endl;
  }
}

Das Ganze jetzt in eine iterative Lösung umzubauen sei den Threadersteller zur Übung überlassen - Tip: es braucht nur 2 geschachtelte for-schleifen

hallo vielen dank, habs mal ausprobiert aber ist nicht so ganz das was ich wollte.

wenn ich zb. 5 reihen mache dann kommt zb
1 1 1 1 8
dann
1 1 1 2 7
dann
1 1 1 3 6

usw.

jedenfalls kommt zb.

1 1 2 1 7 nicht mehr vor

bin grade dabei es iterativ zu machen, aber bis jetzt habe ich auch noch nicht alle kombinationen

viele dank bis hier hin für die mühen, hab schon langsam kein bock mehr )-:

double gesamtLaenge=anzahlKammern*steigung*10;
	bool fertig=false;
	bool fastFertig=false;
	int summe=0;
	rotor r;
	for(unsigned int i=0;i<anzahlKammern;i++)
	{

		r.push_back(1);
	}
	int index=anzahlKammern-1;

	for(unsigned int i=0;i<anzahlKammern;i++)
	{
		summe+=r.at(i);
	}
	if (summe==gesamtLaenge*10)
	{
		rotoren.push_back(r);
	}

	while(!fertig)
	{

		try
		{
			r.at(index)+=delta;
		}
		catch(exception e)
		{
			//cout << system("PAUSE");
			break;

		}
		summe=0;
		for(unsigned int i=0;i<anzahlKammern;i++)
		{	
			summe+=r.at(i);
		}
		if (summe==gesamtLaenge*10)
		{
		//	if(!schonVorhanden(r,anzahlKammern))
				rotoren.push_back(r);
		}

		if(r.at(index)>=gesamtLaenge*10)
		{	
			try
			{
				r.at(index)=1;
				index--;
				if(index<0&&!fastFertig)
				{
					index=0;
					fastFertig=true;
				}
				if(index<0&&fastFertig)
				{
					fertig;
				}
			}
			catch(exception e)
			{
				cout << system("PAUSE");
			}

		}
		if(r.at(index)<gesamtLaenge*10)
		{	
			try
			{
				r.at(index)+=delta;
			}
			catch(exception e)
			{
				cout << system("PAUSE");
			}
			summe=0;
			for(unsigned int i=0;i<anzahlKammern;i++)
			{	
				try
				{
					summe+=r.at(i);
				}
				catch(exception e)
				{
					cout << system("PAUSE");
				}
			}
			if (summe==gesamtLaenge*10)
			{
			//	if(!schonVorhanden(r,anzahlKammern))
					rotoren.push_back(r);
			}
			if(r.at(index)>=gesamtLaenge*10)
			{
				try
				{
					r.at(index)=1;
					index--;
					if(index<0&&!fastFertig)
					{
						index=0;
						fastFertig=true;
					}
					if(index<0&&fastFertig)
					{
						fertig;
					}

				}
				catch(exception e)
				{
					cout << system("PAUSE");
				}
			}
			else
			{
				while(index<anzahlKammern-1)
				{
					index++;
				}
			}
		}

	}

	return false;

pumuckl

mogli3 schrieb:

Das Ganze jetzt in eine iterative Lösung umzubauen sei den Threadersteller zur Übung überlassen - Tip: es braucht nur 2 geschachtelte for-schleifen

hallo vielen dank, habs mal ausprobiert aber ist nicht so ganz das was ich wollte.

wenn ich zb. 5 reihen mache dann kommt zb
1 1 1 1 8
dann
1 1 1 2 7
dann
1 1 1 3 6

usw.

jedenfalls kommt zb.

1 1 2 1 7 nicht mehr vor
[/quote]

naja ist ja im Grunde das Selbe wie 11127 - ich habs extra so eingebaut dass die Summanden immer größer werden.

Wenn du sowas wie 11217 dennoch haben möchtest gibts zwei Möglichkeiten:
a) nimm die Ergebnisse und permutiere ihre Elemente durch (mit std::next_permutation() aus <algorithm>)
b) ersetze min und max in der Schleife:

unsigned int mins = 1;
unsigned int maxs = restsumme - n + 1;

Ich behaupte allerdings mal dass du zumindest auf Variante b) hättest kommen müssen wenn du dich mit dem Code beschäftigt hast und ihn verstanden hast.

du hast recht hab mich nicht ganz damit beschäftigt,
und variante b funktioniert auch, jetzt beschäftige ich mich aber damit, will wissen wie du das gelöst hast.
habs vorher nicht gemacht weil ich noch an meinem code dran saß und das fertig bekommen wollte, nicht aus faulheit.

vielen dank,
viele grüsse und einen schönen abend
mogli

ach und die math bibliothek mit den permutationen an sowas hätte ich nicht gedacht, hab wohl gerade scheuklappen auf.

gruss
mogli3

hallo, hab versucht die rekursive variante iterativ zu machen kriegs aber nicht hin.
weiss zb. nicht wieviele reihen insgesamt gebaut werden und mathematisch konnte ich es mir auch nicht ausrechnen.
haste vielleicht noch ein paar mehr tipps?