C Schleifenproblem

[datalukas]

Also wenn ich das jetzt richtig verstanden habe, muss ich bei Visual C++ hier MPIR, MPFR und vyasm herunterladen. Die Bibliotheken dann in den Visual Studio include bzw. lib-Ordner. Stimmt das?
http://gladman.plushost.co.uk/oldsite/computing/gmp4win.php
Die Alternative wäre, dass ich einfach Ubuntu benutze und hierfür GMP herunterlade.

 

[kuddlmuddl]

Um mit großen ganzzahlen und Brüchen zu rechnen reicht wohl MPIR
MPRF braucht man scheinbar nur um double und float zu ersetzen und vyasm find ich nich^^

Falls du unter Ubuntu entwickeln willst wäre mein Tipp:
Oracle VirtualBox und in dieser Virtual Machine installieren. Das spart viel Arbeit und nervt nich mit dem Bootmanger oder so rum. Dafür arbeitest du natürlich nur "virtuell" was je nach Hardware und Anwendung auch auffallend langsamer sein kann.
Wenns dir nicht gefällt reichts die VM zu löschen und VirtualBox zu deinstallieren.

 

[Dese]

plattformübergreifende big number lib, die sehr leistungsstark und frei ist:
http://gmplib.org/

vieleicht nützlich in dem zusammenhang. skaliert sehr gut, wird auch für wissenschaftliche projekte genutzt.

 

[datalukas]

Ich hab Ubuntu eh schon auf einer VM (vmware), daneben noch Debian und Fedora (letzteres kommt aber wieder runter, weil es damit Probleme gab).

 

[datalukas]

Mit GMP habe ich im Moment noch ein Problem. Für Rest brauche ich diese Funktion:
unsigned long int mpz_tdiv_ui (mpz_t n, unsigned long int d)
http://gmplib.org/manual/Integer-Division.html

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

main()
{
	int y = mpz_tdiv_ui((mpz_t)8,(long unsigned int)6);
	gmp_printf("%Zd", y);
	return 0;
}

Die Parameter müssen per Cast übergeben werden. Beim reinen Testen der Funktion gibt es aber schon Probleme. Denn hier kommt dieser Compilerfehler, obwohl das in dieser Schreibweise ja kein Array voraussetzt:

bignumber.c: In function ‘main’:
bignumber.c:15:22: error: cast specifies array type

Zum Test habe ich mal mpz_t durch mpz_ptr ausgetauscht, dann hat er kompiliert, aber bei Laufen kam dieser Fehler:

Segmentation fault (core dumped)

Eine Frage abseits:

Das Programmieren mit GMP ist weniger systemnah, oder?

 

[nullPtr]

Wie kommst du darauf, die 8 zu casten? Weißt du, was ein C-Cast tut? Wenn nicht, lies es bitte nach, sonst wirst du in Zukunft in haufenweise Fehler laufen.

Probier's mal eher so:

  mpz_t a;
  mpz_init(a);
  mpz_set_ui(a, 8);
  unsigned long i = mpz_tdiv_ui(a, 6);
  printf("%lu\n", i);

 

[datalukas]

Den Cast hab ich deswegen gemacht, weil ohne diese Meldung kam:

bignumber.c: In function ‘main’:
bignumber.c:15:2: warning: passing argument 1 of ‘__gmpz_tdiv_ui’ makes pointer from integer without a cast [enabled by default]
In file included from bignumber.c:3:0:
/usr/local/include/gmp.h:1078:34: note: expected ‘mpz_srcptr’ but argument is of type ‘int’

Mit deinem Code gehts, aber komischerweise nur, wenn ich das return 0 weglasse.

 

[nullPtr]

Die Warnung "makes pointer from integer without a cast" sagt dir im Normalfall, dass du etwas tust, das du nicht wolltest. Dann schaut man sich an, in welchen Datentyp man versucht hat zu casten (und stellt nicht einfach einen cast davor)
In unserem Fall ist dies (aus der gmp-i386.h):

typedef __mpz_struct mpz_t[1];

Du hast also versucht, dem Compiler die 8 als __mpz_struct * zu verkaufen (daher der Fehler). Außerdem erklärt das auch den ominösen Fehler "cast specifies array type" (weil du die 8 nach mpz_t gecastet hast). Als du es dann forciert hast, und die 8 explizit in einen Pointer auf ein __mpz_struct konvertiert hast, ist dein Programm gesegfaultet, weil du wahllos auf Adresse 0x8 zugegriffen hast.

Was natürlich einfacher geht, ist: Man schaut in der libgmp-Doku nach, wie man einen mpz_t korrekt herstellt

 

[datalukas]

Warum der als Array mit Größe eins definiert wurde, ist mir nicht ganz klar. Wenn ich jetzt eine Funktion schreibe (scheinbar gibt es im gmp-Projekt keine Rest-Funktion für beliebig große Werte, sondern nur für Integer), ist das ein kleines Problem. Soweit ich jetzt weiß, muss die Funktion wohl als __mpz_struct deklariert werden. Dann kann ich aber nicht die mpz_t-Funktionen (init, set) benutzen.

 

[Hancock]

Wahrscheinlich werde bei der Bibliothek alle Werte per Referenz übergeben, um das Kopieren der Werte zu vermeiden.
Daher gibt es zwei Möglichkeiten:

1. Du definierst dir die Datentypen ganz normal also "BigInteger a;"
Dann musst du aber bei jedem Funktionsaufruf ein "&" schreiben ("multiply(&a,&b,&erg);")

2. Du definierst dir die Datentypen immer als ein einelementiges Array ("bigInteger a[1];")
Dann kannst du die ganzen "&" weglassen, weil eine Referenz in C quasi gleichbedeutend mit einem Zeiger auf ein Datentyp und damit einem Array ist.

 

[datalukas]

So, nun bin ich fast fertig:

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

void setzeRest(mpz_t zahl, mpz_t teiler, mpz_t returnnumber)
{
	mpz_t multiplikator;
	mpz_init(multiplikator);
	mpz_t hilf;
	mpz_init(hilf);
	mpz_fdiv_q(multiplikator, zahl, teiler);
	mpz_mul(hilf, multiplikator, teiler);       
	mpz_sub(returnnumber, zahl, hilf);
}
   
main()
{
	int i;
	mpz_t potenz1, potenz2, rest, summe;
	mpz_init(potenz1);
	mpz_init(potenz2);
	mpz_init(rest);
	mpz_init(summe);
	mpz_set_ui(summe, 0);
	mpz_t ziffern[350];
	mpz_array_init(ziffern[0], 350, 8);
	mpz_t zweihochtausend;
	mpz_init(zweihochtausend);
	mpz_set_d(zweihochtausend, pow((double)2, (double)1000));
	for(i = 1; i<= log10(pow((double)2, (double)1000))+1; i++)
	{
		mpz_set_d(potenz1, pow((double)10, (double)i));
		mpz_set_d(potenz2, pow((double)10, (double)(i-1)));
		setzeRest(zweihochtausend, potenz1, rest);
		mpz_fdiv_q(ziffern[i], rest, potenz2);
		mpz_add(summe, summe, ziffern[i]);
		gmp_printf("%Zd\n", summe);
	}
	gmp_printf("%Zd", summe);
	return 0;
}

Eine Funktion für den Rest hätte es jetzt doch gegeben, aber so hab ich immerhin noch was dazu gelernt. Da ja keine return-Funktionen möglich sind, musste ich die Funktion als void programmieren. Beim Schema der Rest-Funktion habe ich mich übrigens an meinem eigenen Vorschlag orientiert, falls ihr bei der Funktion die Übersichtlichkeit verliert:

double gibRest(double teiler1, double teiler2)
{
    double multiplikator = teiler1 / teiler2;
    return teiler1 - teiler2 * (int) multiplikator;
}

Ansonsten agiert das Programm so wie in Post #116.
Das Ergebnis ist etwas zu hoch, nämlich 1379 (richtig wären laut Lösung 1366).
Also hab ich mir das Ganze mal im Detail angeschaut. 2 hoch 1000 ist diese Zahl:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Wenn man sich jetzt den Anfang und das Ende des Ausgabe des Programms ansieht (das Programm beginnt mit der letzten Ziffer), sieht man, dass hier eigentlich richtig gerechnet wurde. Die letzte Ziffer ist 6, die vorletzte 7 (die Summe ist also 13), dann 13 + 3 = 16, 16 + 9 = 25 usw. Passt also.

6
13
16
25
31
31
39
...
1351
1351
1357
1365
1365
1370
1371
1378
1378
1379

Das Ende ist eigentlich auch richtig. Die erste Ziffer ist 1, also 1379 - 1 = 1378, dann 1378 - 0 = 1378, dann 1378 - 7 =1371.
Insoweit ist mir schleierhaft, wo da der Fehler steckt. Hab jetzt natürlich nicht alles durchgezählt, aber eigentlich müsste es ja überall funktionieren.

 

[Hancock]

mpz_set_d(zweihochtausend, pow((double)2, (double)1000));
pow liefert ja ne double, die wahrscheinlich/ziemlich sicher 2^1000 gar nicht exakt darstellen kann.

Idee: zweihochtausend=1;for(int i=0;i<1000;++i)zweihochtausend*=2;

 

[datalukas]

Doch, kann es, das hab ich ausprobiert (daher habe ich auch die Zahl im letzten Post von mir), hat mich aber auch verwundert.
Ansonsten würde es auch nicht die letzten Ziffern richtig addieren, denn die wären einfach alle null.

 

[Hancock]

Ok, hast recht, 2^1024 müsste das Limit für Doubles sein und 2^x ist per Definition exakt.

Aber wie sieht's mit 10^200 z.B. aus, da könnte dir die Rundung richtig reinhauen.

Mein Tipp:

int i=2^1000;
int qsum=0;
while(i){
qsum+=i%10;
i/=10;
}
echo qsum;

Dadurch ist keine 10-er Potenz nötig und es sollte funktionieren (und du brauchst nicht alle 302 Ziffern als BigInt-Array abzuspeichern).

 

[datalukas]

Gut, jetzt gehts. Aber nur mit einer for-Schleife. while(zweihochtausend) führte zwar auch zum Ergebnis, aber mit einer Endlosschleife danach. Auch die Definition einer Variable one mit dem Wert 1 (muss man ja bei mpz_ts so machen, und dann dieser Ausdruck hat nicht geholfen:

while(zweihochtausend > one)

Wie kommst du eigentlich auf 2^1024. Ein double hat doch 64 Bit, sollte doch also nur bis 2^64 speichern können, oder?

Außerdem hab ich jetzt Problem 17 gemacht:

#include <stdio.h>
int numberofletters(int x)
{
  if(x < 20)
  {
    switch(x)
    {
      case 1: return 3;
      case 2: return 3;
      case 3: return 5;
      case 4: return 4;
      case 5: return 4;
      case 6: return 3;
      case 7: return 5;
      case 8: return 5;
      case 9: return 4;
      case 10: return 3;
      case 11: return 6;
      case 12: return 6;
      case 13: return 8;
      case 14: return 8;
      case 15: return 7;
      case 16: return 7;
      case 17: return 9;
      case 18: return 8;
      case 19: return 8;
    }
  }
  else
  {  
    if(x < 100)
    {
      switch(x/10)
      {
	case 2: return 6 + numberofletters(x%10);
	case 3: return 6 + numberofletters(x%10);
	case 4: return 5 + numberofletters(x%10);
	case 5: return 5 + numberofletters(x%10);
	case 6: return 5 + numberofletters(x%10);
	case 7: return 7 + numberofletters(x%10);
	case 8: return 6 + numberofletters(x%10);
	case 9: return 6 + numberofletters(x%10);
      }
    }
    else
	return numberofletters(x/100) + 10 + numberofletters(x%100);
  }
}
	
      
      
main (void)
{
  int i;
  int sum = 7; //one thousand
  for(i = 1; i < 1000; i++)
    sum = sum + numberofletters(i);
  printf("%i", sum);
}

Mein Schema für die Wortzusammensetzung:

under 10:
one (3), two (3), three(5), four(4), five(4), six(3), seven(5), eight(5), nine (4)
under 13:
ten (3), eleven (6), twelve (6)
under 20:
thirteen (8), fourteen (8), fifteen (7), sixteen (7), seventeen (9), eighteen (8), nineteen (8)
over 20 under 100:
first digit + second digit
20:
twenty (6) + second digit
30:
thirty (6) + second digit
40:
forty (5) + second digit
50:
fifty (5) + second digit
60:
sixty (5) + second digit
70:
seventy (7) + second digit
80:
eighty (6) + second digit
90:
ninety (6) + second digit
over 100:
first digit + hundred + and (10) + second digit and/or third digit

Das Ergebnis ist auf meiner Ubuntu-VM komischerweise 373500658 und unter Visual C++ 21147, wobei 21124 richtig wären. Evtl. hängt das mit dem Datentyp zusammen, aber das sollte der eigentlich speichern können.

 

[Hancock]

Ähhm, du kannst doch die mpz_t gar nicht direkt vergleichen...

double kann 2^1023 speichern, weil (siehe Wikipedia) der maximale Wert für den Exponenten 1023 ist, dies kann exakt abgespeichert werden, da Binärsystem. 10^300 geht halt nicht, weil da die Präzision nicht ausreicht.

Warum unter Ubuntu jetzt so was komisches rauskommt, gute Frage... sieht aus wie ne Speicheradresse.

 

[datalukas]

So, ich melde mich mal wieder. Ich hab jetzt länger nichts gemacht und wäre jetzt bei Problem 20. Dafür will ich hier aber noch mal was wegen Problem 18 fragen. Ich weiß, diese Lösung wird für euch wahrscheinlich haarsträubend sein, allerdings war das so für mich eigentlich die einzige Möglichkeit, alle Möglichkeiten durchzuprobieren (allerdings ist mir klar, dass das auch mit zwei for-Schleifen geht, ist aber schwerer nachvollziehbar für mich).

#include "stdafx.h"

int main()
{
	int test;
	char triangle[] = "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 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 09 70 98 73 93 38 53 60 04 23";
	int zahlenarray[110];
	int sum;
	int max = 0;
	for(int i = 0; i<= 109; i++) //Belegung des arrays mit den Felder der Zahlenpyramide
	{
		zahlenarray[i+1] = 10*(triangle[i*3]-'0') + (triangle[(i*3)+1]-'0');
	}
	//Schleifen in Kommentar
	printf("%i", max);
	scanf("%i", &test);
	return 0;
}

for(int a = 1; a < 3; a++) //Durchprobieren zeilenweise, Schleifen immer ausgehend von vorheriger
{
sum = 75 + zahlenarray[a];
for(int b = a+2; b <= a+3; b++)
{
sum = sum + zahlenarray;
for(int c = b+3; c <= b+3; c++)
{
sum = sum + zahlenarray[c];
for(int d = c+4; d <= c+5; d++)
{
sum = sum + zahlenarray[d];
for(int e = d+5; e <= d+6; e++)
{
sum = sum + zahlenarray[e];
for(int f = e+6; f <= e+7; f++)
{
sum = sum + zahlenarray[f];
for(int g = f+7; g <= f + 8; g++)
{
sum = sum + zahlenarray[g];
for(int h = g+8; h <= g+9; h++)
{
sum = sum + zahlenarray[h];
for(int i = h+9; i <= h+10; i++)
{
sum = sum + zahlenarray;
for(int j = i+10; j <= i+11; j++)
{
sum = sum + zahlenarray[j];
for(int k = j+11; k <= j+12; k++)
{
sum = sum + zahlenarray[k];
for(int l = k+12; l <= k + 13; l++)
{
sum = sum + zahlenarray[l];
for(int m = l+13; m <= l+14; m++)
{
sum = sum + zahlenarray[m];
for(int n = m+14; n <= m+15; n++)
{
sum = sum + zahlenarray[n];
if(sum > max)
max = sum;
printf("%i \n", sum);
}}}}}}}}}}}}}}

Auch wenn das alles andere als sinnvoll ist: Wo ist hier der Fehler?

 

[kuddlmuddl]

Sorry wenn ich das so deutlich sage und bitte sei nicht beleidigt aber:

Die Tatsache, dass du diese grausamen Lösungsansätze nicht nur in erwägung ziehst sondern sogar programmierst zeigt, dass du immer noch nicht den Sinn hinter der Seite verstanden hast...
Es geht später um "spannende" mathematische Probleme (hier noch nicht) aber AUCH und VOR ALLEM darum, für Probleme elegante Lösungen zu finden!
Du hast viel mehr davon wenn du einige Stunden über eine elegante Lösung nachdenkst und diese dann programmierst als wenn du mit so einer "ich haue stundenlang gräßlichen Code hin und hake das Problem dann als <gelöst> ab" Einstellung voranschreitest.

Dieses Problem schreit gerade zu nach Breiten- oder Tiefensuche und evtl auch Rekursion.

Das erste was du noch vor dem Programmieren machen solltest ist dir überlegen: Wie speichere ich diese Pyramide sinnvoll, um später unkompliziert damit arbeiten zu können?
Hier bietet sich eine Datenstruktur an, welche genau auf das Problem 18 und später auch auf Problem 67 passt:
Ein Binärbaum! Jeder "Knoten" (jede Zahl) hat genau 1 Vorgänger und genau 2 Nachfolger (oder er ist das Ende - also ein Blatt)
Für Bäume gibt es natürlich schon fertige Implementationen oder du baust halt eine selbst.
Dabei würdest du viel viel mehr über Programmieren lernen als wenn du dich nur "IRGENDWIE" zur Lösung kämpfst.

Wenn dir das mit dem Baum zu kompliziert ist ginge auch eine einfache Matrix (dh ein 2D-int-Array):

3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

Wenn man die Daten mittels x (nach rechts) und y (nach unten) Index erreichen kann hat eine Zahl folgende Nachbarn:

gibKoordinatenFolgezahl1(int x, int y, int& folgezahl_x, int& folgezahl_y)
{
  nachbar_x = x;
  nachbar_y = y+1;
}
gibKoordinatenFolgezahl2(int x, int y, int& folgezahl_x, int& folgezahl_y)
{
  nachbar_x = x+1;
  nachbar_y = y+1;
}

Wenn du nicht nur C sondern C++ (oder irgendwas anderes Objektorientiertes) nimmst könntest du dafür auch wunderbar eine Klasse schreiben die die Daten versteckt und dir einfach Schnittstellen - also Methoden - zur Verfügung stellt wie zB "gibWertVonFolgezahl1".

Der Unterschied zwischen Problem 18 und Problem 67 ist dann die Art wie man in den Daten den hochwertigsten Weg sucht:
Hier ist "Brute-Force" (breiten oder tiefensuche) erlaubt aber bei 67 wirst du damit zu lange brauchen (die Anzahl der Möglichkeiten steigt exponentiell). Für Problem 67 bietet sich dann also Wegfindung (A* etc klick) an.

 

[maxwell-cs]

das schreit eher nach dynamischer programmierung

hast allgemein aber schon recht, dass es nicht darum geht, irgendwie eine korrekte lösung zusammenzuhacken.

 

[datalukas]

Ich hab ja schon gesagt, was ihr davon halten werdet.

In einigen Lösungen habe ich auch schon geschaut, und die arbeiten auch nach dem Prinzip in Post #138. Die Speicherung der Daten ist völlig nachvollziehbar, es war etwas anderes, was mich daran abgeschreckt hat.
Wenn ich jetzt mal so mache, dann speichere ich den Baum so ab (der Einfachkeit halber aus der Lösung kopiert):

int baum [][] = 
{
                {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}
}

Nun bräuchte ich einen Hauptschleife, die 2^14 mal (16384) durchlaufen wird.

for(int i = 1; i <= 16384; i++)
	{
		for(int x = 0; x<= 14; x++)
		{
			summe += triangle[x][reihe];
		}
	}

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. In dieser Lösung in C# steht da z.B. folgende Ausdruck:
http://www.mathblog.dk/project-euler-18/

index = index + (i >> j & 1);

So was habe ich allerdings nicht behandelt (wenn das mit C überhaupt so geht), deswegen weiß ich nicht, was da gemacht wird. Scheinbar wird ein Vergleich von i und j durchgeführt und das zu index dazugezählt. Das würde aber bedeuten, dass der Vergleich irgendwann immer gleich ausgehen würde, da i irgendwann zu groß wird.

Sorry, aber das will einfach nicht in meinen Kopf rein.