Zadatak - rekurzija

Evo rješenja u Pythonu 3 (prepisan A* algoritam s Wikipedije)

import random

def valid(v):
    return 0 <= v < 5

def neighbor_nodes(node):
    neighbors = ((node[0] + 1, node[1] - 1),
         (node[0] + 1, node[1]),
         (node[0] + 1, node[1] + 1))
    return (n for n in neighbors if valid(n[0]) and valid(n[1]))

def aStar(A, start):
    openSet = {start}
    closedSet = set()
   
    g_score = {start: 0}

    while openSet:
        current = min(openSet, key=lambda n: g_score[n])
        if current[0] == 4:
            return g_score[current]
       
        openSet.remove(current)
        closedSet.add(current)
        for neighbor in neighbor_nodes(current):
            tentative_g_score = g_score[current] + A[neighbor[0]][neighbor[1]][1]
            if neighbor in closedSet and tentative_g_score >= g_score[neighbor]:
                continue
               
            if (neighbor not in openSet) or tentative_g_score < g_score[neighbor]:
                g_score[neighbor] = tentative_g_score
                openSet.add(neighbor)

    raise Exception('Failure')
       
R = [[((row, col), random.randrange(10)) for col in range(5)] for row in range(5)]

for r in R:
    print([c[1] for c in r])

stupac = int(input('Unesi stupac:'))
if not valid(stupac):
    raise ValueError('Stupac mora biti u intervalu 0-4')

print(aStar(R, (0, stupac)))

Zaboravio sam napisat da mi treba u C-u. Ugl hvala, ali nije to to šta bi trebala radit :( Znaci trebali bi na pocetku alocirat matricu 5x5 (dvodimenzionalni niz), onda izaberemo iz koje kolene krecemo i tada ulazimo u petlju(valjda) koja ce trazit najkraci put od vrha prema dolje(npr kao što je na slici) i napisat na kraju da je npr. Najkraci put: 18 i onda provjerimo po matici dal je dobro.

A ovisi, koji je najkraci put, ja sam bezvene npr napisao sta bi na kraju program trebao vratit, Da je ukupni zbroj brojeva nor 16 i da je to najkraci put ako smo krenuli npr iz 3 kolone..ali ovisi, ja radim sa random brojevima u matrici, znači svaki put će biti drugaciji najkraci put. Mora provjeravat, ne znam kako bi obajsnio ako nisi skuzio. Slika je samo primjer.

Ako reci da je ovo nasa matrica

1  4  5  8  8

1  7  6  0  2

9  7  2  8  2

7  5  2  0  6

0  2  4  6  3

i npr krecemo iz trece kolene(od broja 5), i spuštamo se i provjeravamo koji nam je najkraci put. I sad onda on zbraja 5+7=12 pa 5+6=11, 5+0=5 i pamti, pa ide dalje: kod 5+7=12 moze gledat 5+7+9 ili 5+7+7 ili 5+7+2, pa tako provjerava i 5+6+... i 5+0+..., i tako dog ne najde najkraci put, u ovom primjeru 5+0+2+0+3=10. I ispise najkraci put: 10. Ali to je kad krecemo iz kolone 3. Da smo krenuli iz kolone 1, najkraci put bi bio 1+1+7+2+2=13. Kuzis?

ok bude, hvala unaprijed!

Nije to to, krivo radli, ali svejedno hvala na pokušaju. Neću te više gnjavit, budem se nekako snašao.

Hvala na trudu!

Algoritam ti ne radi jer odabireš najmanjeg susjeda na slijedećem nivou. To slučajno prolazi kod matrice iz primjera, ali nastaje problem kad matrica izgleda ovako:

0  0  0  0  0
9  9  9  8  9
0  9  9  8  9
0  9  9  8  9
0  9  9  8  9

Ako se odabere stupac 2 tvoj program izbacuje da je najmanja suma 32 jer odabire ovakav put:

0  0 0  0  0
9  9  9 8  9
0  9  9 8  9
0  9  9 8  9
0  9  9 8  9

Pravo rješenje je 9, uz ovakav put:

0  0 0  0  0
9 9  9  8  9
0  9  9  8  9
0  9  9  8  9
0  9  9  8  9

Primjer rješenja U Pythonu 3:

def minimalna_suma(row, col, A):
    if row == 4:
        # suma 4. retka je vrijednost stupca
        return A[row][col]
    else:
        # susjedni stupci su (col-1, col, col+1), paziti da se ne pređe rub matrice
        susjedi = (i for i in (col - 1, col, col + 1) if 0 <= i < 5)

        # suma je vrijednost stupca + najmanja suma susjeda iz slijedećeg retka
        return A[row][col] + min(minimalna_suma(row + 1, c, A) for c in susjedi)

# testna matrica
M = [[0,0,0,0,0],
    [9,9,9,8,9],
     [0,9,9,8,9],
     [0,9,9,8,9],
    [0,9,9,8,9]]
# ispis
for r in range(5):
    print(' '.join(str(M[r][c]) for c in range(5)))

kolona = int(input('Stupac:'))
print(minimalna_suma(0, kolona, M))

U tekstu piše da se traži algoritam koji "pronalazi put od vrha do dna tako da suma brojeva na putu bude minimalna".

Ja sam u prvom rješenju napravio suprotnu grešku. Pročitao sam tekst, ali nisam pogledao sliku - mislio sam da su na putu dozvoljeni pomaci gore/dolje/lijevo/desno, a ne samo na donje susjede.

Bobobo-bo Bo-bobo je u pravu! To sam ti htio reci..

npr ovako:

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <time.h>

#define DEFAULT 5

int racunaj(int redak, int stupac, int *p, int n)

{

int min = 0;

int iduci_stupac = stupac;

if(stupac > 0 && stupac < n)

{

min = p[n*redak + stupac - 1];

--iduci_stupac;

if(p[n*redak + stupac] < min)

{

min = p[n*redak + stupac];

++iduci_stupac;

}

if(p[n*redak + stupac + 1] < min)

{

min = p[n*redak + stupac + 1];

iduci_stupac+=2;

}

}

else if(stupac == 0)

{

min = p[n*redak + stupac];

if(p[n*redak + stupac + 1] < min)

{

min = p[n*redak + stupac + 1];

iduci_stupac++;

}

}

else if(stupac == n)

{

min = p[n*redak + stupac - 1];

--iduci_stupac;

if(p[n*redak + stupac] < min)

{

min = p[n*redak + stupac];

++iduci_stupac;

}

}

else return 0;

printf("min= %d\n", min);

if(redak == (n - 1)) return min;

else if(redak < (n-1)) return min + racunaj(redak+1, iduci_stupac, p, n);

else return 0;

}

int main()

{

float broj;

int *p, n;

n = DEFAULT;

p = (int *) malloc (n * n * sizeof (int));

if (p == NULL) printf("Nema dovoljno memorije za ucitati matricu");

else

{

int i, j, redak, stupac, suma = 0;

srand ((unsigned) time(NULL) );

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

broj = (float) rand()/(RAND_MAX+1)*10;

p[i*n + j] = (int) broj;

}

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("%d\t", p[i*n + j]); 

}

printf("\n\n\n");

}

printf("Unesite pocetni stupac (1 - 5):\t");

scanf("%d", &stupac);

stupac -= 1;

printf("Vrijednost stupca je %d\n", p[stupac]);

if(stupac < 0 || stupac > 4)

{

printf("Ne valja!\n\n");

free(p);

return 0;

}

redak = 1;

suma += p[stupac];

suma += racunaj(redak, stupac, p, n);

printf("Minimalna suma: %d\n\n", suma);

}

free(p);

return 0;

}

Samo što ovdje ima grešku da nema granice za matricu kad se izabare 4 ili 5 kolona..