C Schleifenproblem

Hancock · 27. Juli 2013

Also das ist eine gültige C-Anweisung.
i>>j verschiebt i um j Stellen nach rechts (binär), also quasi i*2^j
& macht dann das binäre UND. &1 "extrahiert" also das letzte Bit.

Ob jetzt bei i>>j&1 i>>(j&1) oder (i>>j)&1 heißt, weiß ich grad nicht auswendig...

Also meine Schleife wäre grob gewesen:

Code:

int baum...;
for(int i=13;i>=0;--i){
for(int j=0;j<=i;++j){
baum[i][j]=min(baum[i+1][j],baum[i+1][j+1]);
}
}
printf("%i",baum[0][0]);

Freezedevil · 27. Juli 2013

Wie du sagtest ist i>>j eine Rechtsverschiebung, allerdings entspricht das einer Division

Andernfalls könntest du dir die Anweisung i>>j&1 auch sparen, da immer 0 raus käme.

Hancock · 28. Juli 2013

^^ Stimmt, hab's verwechselt... (Also i>>j ist quasi floor(i/2^j))

kuddlmuddl · 28. Juli 2013

Das Problem ist, dass ich nicht genau weiß, wie jetzt die Variable Reihe von i abhängig ist, so dass immer einen anderer Weg gewählt wird.

Die Antwort ist das hier:

When answering the problem with a brute force solution, it is pretty simple to go through the steps, we just need to try all combinations. Since we have a binary choice each time. We can iterate through all possibilities with a normal integer counter, and use the bits of the number to pick the direction left or right. While running through the path, we sum up the numbers and check if they are larger than the current maximum found.

0000 heißt zB, dass immer links gewählt wird. 0111 heißt dann rechts, rechts, rechts, links und 1010 links, rechts, links, rechts

Hancock · 28. Juli 2013

Das ist doch schnarchlahm( O(2^n) ), oder?
Es gibt doch Lösungen mit O(n²).

datalukas · 28. Juli 2013

Okay, jetzt hab ichs. An 1 und 0 für die Abbiegungen hab ich schon mal gedacht, aber wusste nicht, wie ich das jetzt genau machen soll.

Das heißt, ich kann die aktuelle Wahl der nächsten Zahl auch mit Division durch 2er Potenzen von j und %2 (Rest bei Division durch 2) berechnen.

maxwell-cs · 29. Juli 2013

Hancock schrieb:
Das ist doch schnarchlahm( O(2^n) ), oder?
Es gibt doch Lösungen mit O(n²).

es geht sogar in linearer zeit.

Hancock · 29. Juli 2013

? Du musst doch jeden Wert mindestens einmal anfassen? (Ich rechne mit n² Werten bei einer Pyramidenhöhe von n)

datalukas · 2. August 2013

Bin gerade bei Problem 20, muss wegen der Größe der Zahl wieder mit gmp gemacht werden.

Code:

#include <stdio.h>
#include "math.h"
#include "gmp.h"

void fakultaet(int zahl, mpz_t returnvar)
{
  int i;
  mpz_t hilf, eins;
  mpz_init(hilf);
  mpz_init(eins);
  mpz_set_ui(hilf, zahl);
  mpz_set_ui(eins, 1);
  mpz_set_ui(returnvar, zahl);
  for(i = zahl; i > 0; i--)
  {
    mpz_mul(returnvar, returnvar, hilf);
    mpz_sub(hilf, hilf, eins);
  } 
}
main()
{
  int i;
  mpz_t fak100, rest, summe, potenz1, potenz2;
  mpz_t ziffern[158];
  mpz_array_init(ziffern[0], 158, 8);
  mpz_init(fak100);
  mpz_init(rest);
  mpz_init(summe);
  mpz_init(potenz1);
  mpz_init(potenz2);
  fakultaet(100, fak100);
  for(i = 1; i <= 158; i++)
  {
    mpz_set_d(potenz1, pow((double)10, (double)i));
    mpz_set_d(potenz2, pow((double)10, (double)(i-1)));
    mpz_fdiv_r(rest, fak100, potenz1);
    mpz_fdiv_q(ziffern[i], rest, potenz2);
    mpz_add(summe, summe, ziffern[i]);
    gmp_printf("%Zd und %Zd\n", summe, ziffern[i]);
  }
  gmp_printf("%Zd", summe);
  return 0;
}

Nur gibt es diesmal das Problem, dass die letzten Stellen von fak100 mit Nullen belegt, obwohl er das ja eigentlich können müsste, bei 2¹⁰⁰⁰ ging es ja auch. Oder hängt das evlt. mit einem Speicherfehler zusammen?
In der Ausgabedatei ist unten noch ein längerer Fehler zu finden, hier steht was von einem Pointer (wahrscheinlich bezogen auf irgendeinen mpz_t):

Code:

0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
0 und 0
2 und 2
...
559 und 4
563 und 4
568 und 5
569 und 1
571 und 2
577 und 6
579 und 2
*** Error in `./fak100': realloc(): invalid pointer: 0x00007fea840ebea5 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x7f576)[0x7fea84149576]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x300)[0x7fea8414dda0]
/usr/local/lib/libgmp.so.10(__gmp_default_reallocate+0x1c)[0x7fea847a34bc]
/usr/local/lib/libgmp.so.10(__gmpz_realloc+0x3a)[0x7fea847b819a]
/usr/local/lib/libgmp.so.10(__gmpz_tdiv_qr+0x307)[0x7fea847ba727]
/usr/local/lib/libgmp.so.10(__gmpz_fdiv_q+0x8f)[0x7fea847b079f]
./fak100[0x400c06]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf5)[0x7fea840ebea5]
./fak100[0x400909]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:01 524797                             /home/lukas/Documents/fak100
00601000-00602000 r--p 00001000 08:01 524797                             /home/lukas/Documents/fak100
00602000-00603000 rw-p 00002000 08:01 524797                             /home/lukas/Documents/fak100
0084d000-0086e000 rw-p 00000000 00:00 0                                  [heap]
7fea83eb4000-7fea83ec8000 r-xp 00000000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fea83ec8000-7fea840c8000 ---p 00014000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fea840c8000-7fea840c9000 r--p 00014000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fea840c9000-7fea840ca000 rw-p 00015000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fea840ca000-7fea84288000 r-xp 00000000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fea84288000-7fea84487000 ---p 001be000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fea84487000-7fea8448b000 r--p 001bd000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fea8448b000-7fea8448d000 rw-p 001c1000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fea8448d000-7fea84492000 rw-p 00000000 00:00 0 
7fea84492000-7fea84595000 r-xp 00000000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fea84595000-7fea84795000 ---p 00103000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fea84795000-7fea84796000 r--p 00103000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fea84796000-7fea84797000 rw-p 00104000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fea84797000-7fea84804000 r-xp 00000000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fea84804000-7fea84a03000 ---p 0006d000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fea84a03000-7fea84a04000 r--p 0006c000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fea84a04000-7fea84a0d000 rw-p 0006d000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fea84a0d000-7fea84a30000 r-xp 00000000 08:01 790757                     /lib/x86_64-linux-gnu/ld-2.17.so
7fea84c10000-7fea84c13000 rw-p 00000000 00:00 0 
7fea84c2b000-7fea84c2f000 rw-p 00000000 00:00 0 
7fea84c2f000-7fea84c30000 r--p 00022000 08:01 790757                     /lib/x86_64-linux-gnu/ld-2.17.so
7fea84c30000-7fea84c32000 rw-p 00023000 08:01 790757                     /lib/x86_64-linux-gnu/ld-2.17.so
7fffca9da000-7fffca9fb000 rw-p 00000000 00:00 0                          [stack]
7fffca9fe000-7fffcaa00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted (core dumped)

Beim Kompilieren wird in der Hinsicht kein Fehler ausgegeben.

Hancock · 2. August 2013

Ich glaub nicht, dass double so große Zahlen darstellen kann...
Zieh in deiner Schleife einfach die Potenzen hinterher.
potenz2=potenz1;
potenz1*=10;

Und deine 100! ist genaugenommen 100!*100.

Und für den Fehler: Ich denke, dass mpz_array_init gerne ein &Ziffern[0] hätte.

datalukas · 4. August 2013

@ziffern[0] verwarnt er:

Code:

fak100.c:26:3: warning: passing argument 1 of ‘__gmpz_array_init’ from incompatible pointer type [enabled by default]
In file included from fak100.c:3:0:
/usr/local/include/gmp.h:648:21: note: expected ‘mpz_ptr’ but argument is of type ‘struct __mpz_struct (*)[1]’

Und das eigentliche Problem ist ja auch, dass er 100! nicht darstellen kann, sondern die letzten Stellen einfach mit Nullen beschreibt.

Unten kommt jetzt ein anderer Fehler:

Code:

*** Error in `./fak100': realloc(): invalid pointer: 0x00007fa11a2ebea5 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x7f576)[0x7fa11a349576]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x300)[0x7fa11a34dda0]
/usr/local/lib/libgmp.so.10(__gmp_default_reallocate+0x1c)[0x7fa11a9a34bc]
/usr/local/lib/libgmp.so.10(__gmpz_realloc+0x3a)[0x7fa11a9b819a]
/usr/local/lib/libgmp.so.10(__gmpz_tdiv_qr+0x307)[0x7fa11a9ba727]
/usr/local/lib/libgmp.so.10(__gmpz_fdiv_q+0x8f)[0x7fa11a9b079f]
./fak100[0x400c10]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf5)[0x7fa11a2ebea5]
./fak100[0x400909]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:01 524776                             /home/lukas/Documents/fak100
00601000-00602000 r--p 00001000 08:01 524776                             /home/lukas/Documents/fak100
00602000-00603000 rw-p 00002000 08:01 524776                             /home/lukas/Documents/fak100
0124a000-0126b000 rw-p 00000000 00:00 0                                  [heap]
7fa11a0b4000-7fa11a0c8000 r-xp 00000000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa11a0c8000-7fa11a2c8000 ---p 00014000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa11a2c8000-7fa11a2c9000 r--p 00014000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa11a2c9000-7fa11a2ca000 rw-p 00015000 08:01 790290                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa11a2ca000-7fa11a488000 r-xp 00000000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fa11a488000-7fa11a687000 ---p 001be000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fa11a687000-7fa11a68b000 r--p 001bd000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fa11a68b000-7fa11a68d000 rw-p 001c1000 08:01 790807                     /lib/x86_64-linux-gnu/libc-2.17.so
7fa11a68d000-7fa11a692000 rw-p 00000000 00:00 0 
7fa11a692000-7fa11a795000 r-xp 00000000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fa11a795000-7fa11a995000 ---p 00103000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fa11a995000-7fa11a996000 r--p 00103000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fa11a996000-7fa11a997000 rw-p 00104000 08:01 791031                     /lib/x86_64-linux-gnu/libm-2.17.so
7fa11a997000-7fa11aa04000 r-xp 00000000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fa11aa04000-7fa11ac03000 ---p 0006d000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fa11ac03000-7fa11ac04000 r--p 0006c000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fa11ac04000-7fa11ac0d000 rw-p 0006d000 08:01 1065817                    /usr/local/lib/libgmp.so.10.1.2
7fa11ac0d000-7fa11ac30000 r-xp 00000000 08:01 790757                     /lib/x86_64-linux-gnu/ld-2.17.so
7fa11ae10000-7fa11ae13000 rw-p 00000000 00:00 0 
7fa11ae2b000-7fa11ae2f000 rw-p 00000000 00:00 0 
7fa11ae2f000-7fa11ae30000 r--p 00022000 08:01 790757                     /lib/x86_64-linux-gnu/ld-2.17.so
7fa11ae30000-7fa11ae32000 rw-p 00023000 08:01 790757                     /lib/x86_64-linux-gnu/ld-2.17.so
7fff76274000-7fff76295000 rw-p 00000000 00:00 0                          [stack]
7fff763b8000-7fff763ba000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted (core dumped)

datalukas · 6. August 2013

Der Fehler muss irgendwo in der Funktion fakultaet liegen, ab einer bestimmten Größe des ersten Parameters, werden die letzten Stellen einfach mit Nullen belegt. Warum das so ist, ist mir allerdings schleierhaft. Hab auch schon mal doubles statt int zum Zählen verwendet, hat aber natürlich nichts gebracht.

Code:

void fakultaet(int zahl, mpz_t returnvar)
{
  int i;
  mpz_t hilf, eins;
  mpz_init(hilf);
  mpz_init(eins);
  mpz_set_ui(hilf, zahl);
  mpz_set_ui(eins, 1);
  mpz_set_ui(returnvar, zahl);
  for(i = zahl; i > 0; i--)
  {
    mpz_mul(returnvar, returnvar, hilf);
    mpz_sub(hilf, hilf, eins);
  } 
}

BTW:
Gibt es auch ein GCC, das auf dem Stand des Visual C++ C-Compilers ist? Der GCC Compiler akzeptiert nämlich keine Deklarationen in for-Schleifen und auch keine "//"-Auskommentierungen, wobei letzteres bei reinen C-Compilern Standard sein müsste.

TheCadillacMan · 6. August 2013

datalukas schrieb:
Gibt es auch ein GCC, das auf dem Stand des Visual C++ C-Compilers ist? Der GCC Compiler akzeptiert nämlich keine Deklarationen in for-Schleifen und auch keine "//"-Auskommentierungen, wobei letzteres bei reinen C-Compilern Standard sein müsste.

Das geht beides erst ab C99. Dazu musst du mit dem "-std=c99"-Switch kompilieren.

maxwell-cs · 6. August 2013

Hancock schrieb:
? Du musst doch jeden Wert mindestens einmal anfassen? (Ich rechne mit n² Werten bei einer Pyramidenhöhe von n)

ich war davon ausgegangen, dass du mit n die anzahl der knoten des graphs meinst.
kommt dann aufs selbe raus.

ontopic @ datalukas: schau dir mal an, wie fließkommazahlen intern funktionieren und dargestellt werden.

datalukas · 9. August 2013

Code:

ontopic @ datalukas: schau dir mal an, wie fließkommazahlen intern funktionieren und dargestellt werden.

Basiert die Speicherung der mpz_ts denn auf Fließkommazahlen?

Ich hab übrigens schon mal weiter gemacht währenddessen und bin bei Problem 22.

Code:

#include "stdafx.h"


int main()
{
	int test, c;
	int sum = 0;
        long long sum_scores = 0;
	int position = 1;
	FILE *file = fopen("C:\\Users\\Lukas\\Documents\\names.txt", "r");
	do
	{
		c=fgetc(file);
		if(c!=34 && c!= 44)
		{	
			sum += c - 64;
		} 
		else
		{
			if(c==44)
			{	
				sum_scores += sum * position;
				position ++;
				sum = 0;
			}
		}
		printf("%i und %i und %i \n", c, position, sum_scores);
	}
	while(c!=EOF);
	printf("%i", sum_scores);
	scanf("%i", &test);
	return 0;
}

Das Ergebnis ist 849689006, die Lösung sagt 871198282. Habt ihr einen Tipp, was da falsch ist?

TheCadillacMan · 9. August 2013

Die Aufgabe sagt, dass du die Namen zuerst alphabetisch sortieren musst.
(Habs mit einem schnell zusammengeschusterten C#-Programm getestet und bekomme für die sortierte Liste 871198282 raus).

maxwell-cs · 10. August 2013

datalukas schrieb:
Code:

ontopic @ datalukas: schau dir mal an, wie fließkommazahlen intern funktionieren und dargestellt werden.

Basiert die Speicherung der mpz_ts denn auf Fließkommazahlen?

oh, sorry, war aufgrund der typischen symptome der ungenauigkeit von großen fließkommazahlen davon ausgegangen. da tritt nämlich exakt das auf: sehr große zweierpotenzen können exakt dargestellt werden, bei anderen zahlen wird gerundet.

hast du denn mal versucht, wie vorgeschlagen, z.b. aufgabe 18 effizienter zu lösen, sodass du auch aufgabe 67 (dasselbe wie 18, nur eine größere instanz) lösen kannst?
falls du da nicht weiter kommst, können wir dir auch gerne helfen, aber du solltest es zumindest mal versucht und eine weile darüber nachgedacht haben.

dabei würdest du vermutlich deutlich mehr lernen als beim sturen abarbeiten der aufgaben und wechseln zur nächsten aufgabe, sobald eine lösung gefunden ist, die "irgendwie" funktioniert.

wenn dir 18 nicht gefällt, kann man auch bei aufgabe 24 ganz gut den unterschied zwischen effizient und bruteforce lernen.

7H3 N4C3R · 15. August 2013

datalukas schrieb:
Das Ergebnis ist 849689006, die Lösung sagt 871198282. Habt ihr einen Tipp, was da falsch ist?

Hübscher Bug

Hab aber auch nen Moment gebraucht, bis ich es gesehen habe.

Die fehlende Sortierung hat TheCadillacMan ja schon erwähnt.

Das Ergebnis für die unsortierte Liste sollte 850081394 sein. Schau dir mal deinen Code an, was mit dem letzten Namen der Liste passiert...

datalukas · 17. August 2013

@Über mir Du meinst das EOF?
Das mit dem Alphabet hab ich übrigens vergessen.

Aber wie geraten, habe ich mich jetzt nochmal mit einer anderen Lösung des Problem 18 beschäftigt.
Das wäre mein Ansatz:

Code:

#include "stdafx.h"

int main()
{
	int test, c, max_r, max_z; 
	int max, x, y;
	max = x = y = 0;
	int zahlen[15][15];
	int zahlen_list[15][15]; //Listenzugehörigkeit eines Knotens, 1 Open List, 2 Closed List
	int f[15][15]; //F-Wert (höchster anzunehmender Wert eines Knotens)
	FILE *file = fopen("C:\\Users\\Lukas\\Documents\\binärbaum.txt", "r");
	c = fgetc(file);
	for(int i = 0; i<=14; i++)
	{
		for(int n = 0; n<=14; n++)
		{
			f[i][n]=15*99; //höchster möglicher Wert
			zahlen_list[i][n] = 0; //Zunächst kein Knoten in einer Liste
		}
	}
        //Speicherung der Zahlen in Array 
        do
	{
		zahlen[x][y] = (c - 48) * 10 + fgetc(file)-48;
		c = fgetc(file);
		if(c == 32)
		{
			y++;
		}
		else
		{
			y = 0;
			x++;
		}
		c = fgetc(file);
	}
	while(c != EOF);
	f[0][0] =  75 + 14 * 99;
	while(/*Kein f-Wert größer als ein abgeschlossener Weg ist*/)
	{
		/*Fortfahren mit dem Knoten, der den größten F-Wert besitzt
		Dazu werden die Array-Positionen des Knotens als Variablen max_z und max_r gespeichert*/
		for(int i = 0; i<=14; i++)
		{
			for(int n = 0; n<=14; n++)
			{
				if(f[i][n]>max)
				{
					f[i][n] = max;
					max_z = i;
					max_r = n;
				}
			}
		}
		//Untersuchung des größeren Nachfolgeknotens
		if(f[max_z+1][max_r]>f[max_z][max_r+1]) 
		{
			f[max_z+1][max_r] = f[max_z][max_r] - 99 + zahlen[max_z+1][max_r];
			zahlen_list[max_z+1][max_r] = 1;
		}
		else
		{
			f[max_z+1][max_r+1] = f[max_z][max_r] - 99 + zahlen[max_z+1][max_r+1];
			zahlen_list[max_z+1][max_r+1] = 1;
		}
		//Falls beide Nachfolgeknoten untersucht sind, kommt der Knoten auf die Closed List
		if(zahlen_list[max_z+1][max_r]==1 && zahlen_list[max_z+1][max_r]==1)
			zahlen_list[max_z][max_r]=2;
	}
	scanf("%i", &test);
	return 0;
}

Bevor ich jetzt so weiter mache, wollte ich erstmal wissen, was ihr davon haltet. Zu machen wäre noch die Bedingung der Hauptschleife, wohl über eine bool-Funktion.

Allerdings frage ich mich, man sich diese Open List und Closed List nicht auch sparen könnte. Müsste diese Lösung nicht auch auf diese Weise und mindestens genauso effizient zum Ergebnis führen?

Code:

#include "stdafx.h"
#include "math.h"

int main(void)
{
	int test;
	int spalte, summe;
	int max = 0;
	int baum [15][15] = 
	{
        {75},
		{95,64},
		{17,47,82},
		{18,35,87,10},
		{20,04,82,47,65},
		{19,01,23,75,03,34},
		{88,02,77,73,07,63,67},
		{99,65,04,28,06,16,70,92},
		{41,41,26,56,83,40,80,70,33},
		{41,48,72,33,47,32,37,16,94,29},
		{53,71,44,65,25,43,91,52,97,51,14},
		{70,11,33,28,77,73,17,78,39,68,17,57},
		{91,71,52,38,17,14,91,43,58,50,27,29,48},
		{63,66,04,68,89,53,67,30,73,16,69,87,40,31},
		{04,62,98,27,23, 9,70,98,73,93,38,53,60,04,23}
	};
	for(int i = 0; i < 16384; i++)
	{
		summe = 75+14*99;
		spalte = 0;
		for(int x = 1; x<= 14; x++)
		{
			spalte += (i % (int) pow((double)2, (double) x)) / (int)pow((double)2, (double) x-1);
			summe = summe - 99 + baum[x][spalte];
			if(summe < max)
				break;
		}
		if(summe > max)
			max = summe;
	}
	printf("%i", max);
	scanf("%i", &test);
	return 0;
}

Richtig ist sie jedenfalls, und auch hier wird ein Pfad nicht mehr weiter "erschlossen", wenn der höchste anzunehmende Endwert kleiner als die bisher größte Summe ist.

Hancock · 18. August 2013

Also mal zu deinem zweiten Codeteil...

Das ist immer noch eine Brute-Force-Lösung und scheitert dann beim Baum in Aufg. 22 (int mit 99 stellen).
Außerdem ist das mit (int)pow(...) grässlich (nehm 1<<x dafür). Und auch nicht arg clever. spalte+=i&(1<<x)?1:0;

Für die Lösung: Denk "Rückwärts" also das Dreieck von unten nach oben und welche Infos du abspeichern kannst.

C Schleifenproblem

Captain

Lieutenant

Captain

Commander

Captain

Captain

Lt. Junior Grade

Captain

Captain

Captain

Captain

Captain

Captain

Lt. Junior Grade

Captain

Captain

Lt. Junior Grade

Lt. Commander

Captain

Captain

Ähnliche Themen