Największa suma w trójkącie liczb

[steal]

Zaczynając od wierzchołka, przemieszczamy się między wierszami wybierając liczbę która sąsiaduje z poprzednią w wierszu powyżej. Maksymalna suma wybranych liczb dla poniższego trójkąta wynosi 23:

3
7 5
2 4 6
8 5 9 3

To jest, \(\displaystyle{ 3 + 7 + 4 + 9 = 23.}\)

Znajdź maksymalną sumę dla poniższego trójkąta:

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 09 70 98 73 93 38 53 60 04 23

Moje pytanie jest następujące: jak wygląda algorytm który znajdzie tą sumę?
(Szukanie brutal force'm odpada).

[eloar]

W zasadzie, to trzeba okreslic co oznacza sasiedztwo liczb . Wiec jak mamy liczbe o indexie n wybrana, to konieczne jest w nastepnym wierszu wybranie liczby o indexie n-1 || n || n+1 czyli algorytm w skrocie moze wygladac jakos tak:

Kod: Zaznacz cały

main()
{
  int tr[MAX][MAX],n,i,sum;
  n=0;
  sum=0;
  //wczytaj trojkat licz gdzies tutaj do tablicy tr
  for(i=0;i<MAX;i++)
  {
    a=MaxOf3(tr[i][n-1],tr[i][n],tr[i][n+1]);
    if(tr[i][n]!=a)
    {
      if(tr[i][n-1]!=a)
      {
        n=n+1;
      }
      else n=n-1;
    }
    sum+=a;
  }
}

Funkcja MaxOf3 zwraca wartosc najwiekszego z podanych 3 argumentow. Chyba nie powinno byc trudno napisac ja samemu. Zawsze znajdziesz w ten sposob najwieksza z 3 sasiadujacych liczb.

[steal]

Emm chyba się nie zrozumieliśmy. Sąsiedztwem w tym przypadku jest styczność dwóch liczb - albo jedna jest po drugą, albo 'dotyka' ją po przekątnej (jak w przykładzie z pierwszego postu).
Wracając do Twojego kodu - w jaki sposób zapewniasz w nim, że dana suma jest maksymalna z możliwych?
Prześledź przykład:

1
1 2
1 2 3
9 1 1 3

Twój algorytm:
1
1 2
1 2 3
9 1 1 3

Poprawna droga:
1
1 2
1 2 3
9 1 1 3

[edit] Oczywiście nadal potrzebuję samej metody, kod jestem w stanie sam napisać

[michand]

Programowanie dynamiczne.

Narysuj sobie na kartce drugi taki sam trojkat, a potem wypelnij w nastepujacy sposob zaczynajac od gory:
dla kazdej pozycji w takim trojkacie wpisz najwieksza liczbe, ktora mozna na niej uzyskac w jakikolwiek sposob zgodny z poleceniem. Powinienes otrzymac cos takiego:

Kod: Zaznacz cały

  1
  2 3
  4 5 6
14 7 7 9

Na pierwszej pozycji (od gory, od lewej) stoi 1, bo "inaczej sie nie da". Na kolejnej pozycji jest 2, bo do jedynki na gorze dodajesz jedynke z wyjsciowego kwadratu. Tak samo obok. W kolejnym wierszu jest ciekawiej, bo do 1 z wyjsciowego kwadratu dodajesz 2 lub 3. Wybierasz 3 i wpisujesz 3+1 = 4. Przechodzimy w prawo. Do dwojki dodajesz 2 lub 3. 2 + 3 = 5. I tak dalej az dojdziesz do konca trojkata. A potem max ze wszystkich liczb "podstawy" trojkata i masz wynik. Mozna zrobic jeszcze jeden trojkat, w ktorym zapisywalbys "sciezke", po ktorej doszedles do wyniku, ale tego w poleceniu nie ma.

Mam nadzieje ze o to chodzilo.

Michal

[LastSeeds]

Troche nie doczytalem co miales na mysli ale stworzylem algorytm sumowania najwyzszych liczb w kazdym wierszu moze choc troche pomoze xd

Kod: Zaznacz cały

#include <iostream>
#include <ctime>
using namespace std;

int aLiczba[5000]={0,};//zadeklaruj tablice przechowujaca liczby i wyzeruj
	

int max(int aTablica[],int nIlosc) //przekaz do funkcji tablice liczb
{
	for(int i=1;i<nIlosc;++i) //znajdz max w wierszu
		najwyzsza=(najwyzsza>aTablica[i]?najwyzsza:aTablica[i]);

return najwyzsza;
}

int ObliczSume(int nIloscLiczb)
{
	int suma=0;
	int aTablica[5000]={0,};
	int c;
	int licznik=1;
	int r=0;
//ilosc liczb jest ok

	for(;aLiczba[r]!=0;) //wypisz wszystkie liczby z tablicy
	{
		//wypisz za kazdym razem o 1 wiecej liczb i za kazdym razem liczbe
		// o nastepnym indeksie
		c=licznik;
for(c=0;c<licznik;++c) //dla ilosci liczb zapisuj kolejne indeksy do tablicy
{
	if(aLiczba[r]==0)
		break;
	aTablica[c]=aLiczba[r++];  //co kazda kolejke znajduje wiecej wymazujac
									//poprzednie
}
//przekaz ilosc liczb w wierszu
suma+=max(aTablica,licznik); //przekaz cala tablice i indeks do ktorego ma liczyc max
++licznik;



}
	return suma;

}

int main()
{
	int IloscLiczb=6; //ta liczba musi byc prawidlowa
	srand ((int) time(NULL));

	//wczytaj do tablicy liczby trojkatu
	for(int i=0;i<IloscPieter;++i) //wczytaj losowe liczby dwucyfrowe do tablicy
		aLiczba[i]=rand()%90+10;
int b=i-1; //ilosc liczb w tablicy
	//wypisz trojkat
	int c;
	int licznik=1;
	int r=0;
	for(;aLiczba[r]!=0;) //wypisz wszystkie liczby z tablicy
	{
		//wypisz za kazdym razem o 1 wiecej liczb i za kazdym razem liczbe
		// o nastepnym indeksie
		c=licznik;
for(;c!=0;--c) //dla ilosci liczb wypisuj kolejne indeksy
{
	if(aLiczba[r]==0)
		break;
	cout<<aLiczba[r++]<<" "; 
}
++licznik;

cout<<endl;//przejdz do nastepnej lini

	}
	int suma=ObliczSume(r);
	cout<<endl<<"Suma tego trojkata wynosi: "<<suma;
return 0;
}

[steal]

michand - tak, o to chodziło, dziękuję.
Jest jednak jeden problem, bo w momencie gdy dla podanych tutaj przykładów wyniki są poprawne, to dla zadanego w tym zadaniu trójkąta wynik okazuje się błędny =| Sam nie wiem co o tym sądzić...
Załączam program:

Kod: Zaznacz cały

#include <stdio.h>

int max(int,int);
int maxLastRow(void);
void loadMatrix(void);
void showMatrix(void);

const int N=15; //Ilość wierszy
int A[N][N]; 

void main(void){
	int result;

	loadMatrix();
	showMatrix();

	for (int i=1;i<N;i++)
		for (int j=0;j<=i;j++)
			A[i][j] += max(i,j);

	showMatrix();
	result = maxLastRow();
	printf("Maximum sum: %d.
",result);
}

int max(int n,int m){
	int maximum;
	bool first = true;

	for (int i=m-1;i<=m+1;i++){
		if(i<0 || i>n)
			continue;
		if(first){
			maximum = A[n-1][i];
			first = false;
		}else if(A[n-1][i]>maximum)
			maximum = A[n-1][i];
	}
	return maximum;
}

int maxLastRow(void){
	int maximum = A[N-1][0];

	for (int i=1;i<N;i++)
		if(A[N-1][i] > maximum)
			maximum = A[N-1][i];	
	
	return maximum;
}

void loadMatrix(void){
	FILE *file = fopen("triangle.txt","r");
	for (int i=0;i<N;i++)
		for (int j=0;j<=i;j++)
			fscanf(file,"%d",&A[i][j]);
	fclose(file);
}

void showMatrix(void){
	for (int i=0;i<N;i++){
		for (int j=0;j<=i;j++)
			printf("%d ",A[i][j]);
		printf("
");
	}
	printf("
");
}

Plik triangle.txt

Kod: Zaznacz cały

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 09 70 98 73 93 38 53 60 04 23

LastSeeds - spróbuj przerobić swój program na wczytywanie powyższego trójkąta i wtedy porównamy wyniki
Mój wynik: \(\displaystyle{ 1116}\)

[michand]

A skad wiesz, ze jest bledny? Ile powinno wyjsc?

Michal

[steal]

Zadanie pochodzi ze strony - nie znam poprawnej odpowiedzi, ale moja jest wskazywana jako błędna.

[michand]

Funkcja max() powinna wygladac tak:

Kod: Zaznacz cały

int maxi(int n,int m){
	int maximum = 0;
	if(n > 0 && m > 0)
		maximum = ((A[n-1][m-1] > A[n-1][m]) ? A[n-1][m-1] : A[n-1][m]);
	if(n == 0)
		maximum = 0;
	if(n != 0 && m == 0)
		maximum = A[n-1][m];
	return maximum;
}

Mam nadzieje, ze jej dzialanie jest zrozumiale. Nie rozumiem za to dlaczego w 17tej linii jest

Kod: Zaznacz cały

for (int i=1;i<N;i++)

zamiast i = 0. Po poprawkach Twoj program daje poprawna odpowiedz.

Michal

[steal]

Nie rozumiem za to dlaczego w 17tej linii jest

Kod: Zaznacz cały

for (int i=1;i<N;i++)

zamiast i = 0.

Skoro liczba \(\displaystyle{ A[0][0]}\) jest pierwszą w trójkącie to po co wywoływać dla niej funkcję max()?
A w moim kodzie wystarczyło w 29 linii zmienić warunek na:

Kod: Zaznacz cały

i<=m

Dzięki wielkie za pomoc!

[Dumel]

Zadanie pochodzi ze strony

dzięki za linka. fajna stronka, prawie jak MAIN

[steal]

dzięki za linka. fajna stronka, prawie jak MAIN

Mi również przypadła do gustu To jeżeli jesteśmy przy tym temacie:
Potyczki algorytmiczne
I LO w Tarnowie

pozdrawiam

[LastSeeds]

wyszlo mi 1313 dla twojego trojkata

Kod: Zaznacz cały

75
95 64
17 47 82
18 35 87 10
20 4 82 47 65
19 1 23 75 3 34
88 2 77 73 7 63 67
99 65 4 28 6 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 4 68 89 53 67 30 73 16 69 87 40 31
4 62 98 27 23 9 70 98 73 93 38 53 60 4 23

Suma tego trojkata wynosi: 1313

[steal]

Poprawny wynik to \(\displaystyle{ 1074}\).

pozdrawiam

[Xitami]

75
.. 64
.. .. 82
.. .. 87 ..
.. .. 82 .. ..
.. .. .. 75 .. ..
.. .. 77 .. .. .. ..
.. 65 .. .. .. .. .. ..
.. 41 .. .. .. .. .. .. ..
.. .. 72 .. .. .. .. .. .. ..
.. 71 .. .. .. .. .. .. .. .. ..
70 .. .. .. .. .. .. .. .. .. .. ..
91 .. .. .. .. .. .. .. .. .. .. .. ..
.. 66 .. .. .. .. .. .. .. .. .. .. .. ..
.. .. 98 .. .. .. .. .. .. .. .. .. .. .. ..
Suma 1116, sprawdziłem rekurencyjnie 1201917 "dróg" w mniej niż sekundę.
Liczba możliwości rośnie jak ( )

Chyba, że wolno wędrować w dół i w prawo, wtedy:
75
.. 64
.. .. 82
.. .. 87 ..
.. .. 82 .. ..
.. .. .. 75 .. ..
.. .. .. 73 .. .. ..
.. .. .. 28 .. .. .. ..
.. .. .. .. 83 .. .. .. ..
.. .. .. .. .. 32 .. .. .. ..
.. .. .. .. .. .. 91 .. .. .. ..
.. .. .. .. .. .. .. 78 .. .. .. ..
.. .. .. .. .. .. .. .. 58 .. .. .. ..
.. .. .. .. .. .. .. .. 73 .. .. .. .. ..
.. .. .. .. .. .. .. .. .. 93 .. .. .. .. ..
Suma 1074, możliwości \(\displaystyle{ 2^{n-1}}\)