Gra Skoki - rekurencja

PROGRAM:

• mamy tablice wypełnioną liczbami naturalnymi > 1
• startujemy z pola o indeksie 1
• cel dotrzeć do pola o indeksie MAX
  *RUCHY:
  1. gdy stoimy na polu gdzie jest L.PIERWSZA - cofamy sie o 1 pole
  2. gdy L.ZLOZONA to możemy skoczyć w prawo o liczbę pól będącą czynnikiem pierwszym tej liczby
• mamy k ruchow

uses crt;
const
	max = 10;
type
	taba = array [1..max] of integer;	
var
	i:integer;
	tab: taba;
	
function czy_pierwsza(n:integer):boolean;
var
	i:integer;
	flaga : boolean;
begin	
	i:=2;
	flaga:=true; //zakladamy ze jest l.pierwsza
	if n=1 then flaga:=false;
	while (i<=sqrt(n)) and (flaga=true) do begin
		if n mod i = 0 then flaga:=false;
		i:=i+1;
	end;
	czy_pierwsza:=flaga;
end;	
	
function gra(var t:taba; ind,k:integer):boolean;
var a,b:integer;
begin
	if (k=0) and (ind<>max) then gra:=false {NIE MAMY RUCHOW I  NIE JESTESMY NA KONCY}
		else if ind=max then gra:=true {DOSZLISMY DO KONCA}
		else if (ind>max) or (ind<1) then gra:=false {PRZEKROCZYLISMY TABLICE}
		else if (czy_pierwsza(ind)=true) then gra:=gra(t,ind-1,k-1) {L.PIERWSZA -> COFAMY SIE}
		else
		begin
		{liczba jest zlozona}
			a:=t[ind];
			b:=2;
			while a>0 do begin
				if a mod b=0 then
					begin
						while (a mod b = 0) do a:=a div b;
						gra:=gra(t, ind+b,k-1)
					end;
				b:=b+1;
			end;
		end;
end;


begin
	{LOSOWANIE I WYPISANIE TABLICY DO GRY}
	randomize;
	for i:=1 to max do
		tab[i]:=random(6)+2;
	for i:=1 to max do write(i, ' ');
	writeln;
	for i:=1 to max do write(tab[i], ' ');
	
	
	if gra(tab,1,5)=true then writeln('da sie') else writeln('nie da sie');
end.

 

Gdzie popełniłem błąd? Jak zmienić program, aby wypisywał rozwiązanie?
Z góry dziękuję za pomoc.

A co jeżeli na pierwszym polu już będzie liczba pierwsza?
A co jeżeli przeskoczymy przez MAX?

A co, jeśli rekurencja nie jest potrzebna? (a nie jest, wystarczy zwykła pętla repeat czy while, dla hardkorowców goto)

Coś mi się widzi, że przekombinowałeś i że zasady tej gry są zbyt ogóle i niedopracowane, jak kolega wyżej zauważył wypełnianie "planszy" musi być bardzo staranne, żeby nie dało się wyjść poza zakres (albo zasady ruchu muszą mieć jakieś zabezpieczenia);

Podaj więcej informacji, na kod na razie nie patrzę, bo jak można program napisać do nieuregulowanych zasad gry...

EDIT - rekurencja jest jednak potrzebna, gdy ilość kroków jest ograniczona i poszukujemy najkrótszej drogi, a to się przyda (przeczytałem nieuważnie...);

Zabezpieczenie przed liczbą pierwszą na 1 miejscu i przeskoczeniem max mamy przez to, że sprawdzamy: if (ind>max) or (ind<1) then gra:=false
oraz to, że gra zaczyna się od pola: 1 i tam będzie liczba pierwsza to cofamy się na pole 0.

Gra nie będzie miała więcej zasad. Takie otrzymałem zadanie na kolokwium wczoraj.

furious programming napisał(a):

rekurencja jest jednak potrzebna, gdy ilość kroków jest ograniczona i poszukujemy najkrótszej drogi, a to się przyda (przeczytałem nieuważnie...);
Nie, rekurencja się nie przyda, chyba że poszukujemy nie optymalnego rozwiązania.

Zadanie jest bardzo ciekawe, z tym że przy tych ustawieniach (10 kroków od 2 do 7) rzadko istnieje możliwość zakończenia gry.

uses Math;

const Lmin=2;
const Lmax=7;
const Size=10;
const Tb:array[1..Size]of Word=(4,4,2,4,4,3,4,4,5,7);
var Sito:array[2..Lmax]of Boolean;
var Mat:array[1..Size,1..Size]of Boolean;
var Path:array[1..Size]of Word;
var i,k:Integer;
var W:Word;
var F:Boolean;

begin
  for i:=2 to Lmax do Sito[i]:=false;
  for i:=2 to Lmax do
  begin
    if not Sito[i] then
    begin
      k:=i+i;
      while k<=Lmax do
      begin
        Sito[k]:=true;
        Inc(k,i);
      end;
    end;
  end;
  randomize;
  while true do
  begin
    for i:=1 to Size do Write(i,' ');
    WriteLn;
    for i:=1 to Size do
    begin
      Write(Tb[i],' ');
      Path[i]:=0;
      for k:=1 to Size do Mat[i,k]:=false;
    end;
    WriteLn;
    for i:=1 to Size do
    begin
      W:=Tb[i];
      if Sito[W] then
      begin
        for k:=Trunc(Sqrt(W+1)) downto 2 do
        begin
          if (not Sito[k])and(i+k<=Size)and((W mod k)=0) then Mat[i,i+k]:=true;
        end;
      end
      else if i>1 then Mat[i,i-1]:=true;
    end;
    Path[Size]:=Size;
    F:=true;
    while F do
    begin
      F:=false;
      for i:=2 to Size do
      begin
        if Path[i]<>0 then
        begin
          for k:=1 to Size do
          begin
            if (Path[k]=0)and(Mat[k][i]) then
            begin
              Path[k]:=i;
              F:=true;
            end;
          end;
        end;
      end;
    end;
    if Path[1]=0 then WriteLn('Nie da sie'#10)
    else
    begin
      Write('Da sie:');
      i:=1;
      while i<>Size do
      begin
        Write(' ',i);
        i:=Path[i];
      end;
      WriteLn(' ',Size);
      ReadLn;
    end;
    for i:=1 to Size do Tb[i]:=Lmin+random(Lmax-Lmin+1);
  end;
end.

Wykładowcy chodziło raczej o rozwiązanie tego rekurencyjnie.
Ale dziękuję za takie rozwiązanie.
Czy mógłby ktoś spojrzeć na to co ja wymyśliłem? Ewentualnie zaproponować jakieś inne rekurencyjne rozwiązanie?

problem masz tu:
gra:=gra(t, ind+b,k-1)
jeżeli funkcja zwróciła true to musisz natychmiast zrobić exit;

Poprawiłem trochę kod, nie działa to dobrze, ponieważ po wyjściu z pętli nie zmienia wartości zmiennej k-ruchy, powinno ją przywracać to wartości sprzed nieprawidłowego wejścia, dlatego gdy dodałem 10 program się zakończył.

uses crt;
const
	max = 9;
type
	taba = array [1..max] of integer;	
var
	i:integer;
	tab: taba;
	
function czy_pierwsza(n:integer):boolean;
var
	i:integer;
	flaga : boolean;
begin	
	i:=2;
	flaga:=true; //zakladamy ze jest l.pierwsza
	if n=1 then flaga:=false;
	while (i<=sqrt(n)) and (flaga=true) do begin
		if n mod i = 0 then flaga:=false;
		i:=i+1;
	end;
	czy_pierwsza:=flaga;
end;	
	
function gra(var t:taba; ind,k:integer):boolean;
var a,b:integer;
begin
	writeln('ind= ', ind, ' k= ', k , ' t[ind]= ' ,t[ind]);
		if ind=max then begin gra:=true; writeln('udalo sie');  exit; end 
	{NIE MAMY RUCHOW I  NIE JESTESMY NA KONCU}
		else if (k<1) then begin gra:=false; exit; end    {DOSZLISMY DO KONCA}
		else if (ind>max) or (ind<1) then begin gra:=false; exit; end  {PRZEKROCZYLISMY TABLICE}
		else if (czy_pierwsza(t[ind])=true) then begin writeln('wroc na', ind -1); gra:=gra(t,ind-1,k-1) end {L.PIERWSZA -> COFAMY SIE}
		else
		begin
		{liczba jest zlozona}
			a:=t[ind];
			b:=2;
			while a>0 do begin
				if (a mod b)=0 then
					begin
						while (a mod b = 0) do a:=a div b;
						writeln('skok z ', ind , ' na ', ind+b);
						gra:=gra(t, ind+b,k-1);
						if gra then exit;
						k:=k+10;   //przykladowe dodanie ruchow
						writeln('za petla');
					end;
				b:=b+1;
			end;
		end;
end;


begin
	{LOSOWANIE I WYPISANIE TABLICY DO GRY}
	randomize;
	{for i:=1 to max do
		tab[i]:=random(98)+2;}
	tab[1]:=6;
	tab[2]:=4 ;
	tab[3]:= 3;
	tab[4]:= 6;
	tab[5]:= 3;
	tab[6]:= 3;
	tab[7]:= 4;
	tab[8]:= 3;
	tab[9]:=3;
	for i:=1 to max do write(i, ' ');
	writeln;
	for i:=1 to max do write(tab[i], ' ');
	writeln;	

if gra(tab,1,100)=true then writeln('da sie') else writeln('nie da sie');
end.
 

Proszę o pomoc

Wróć do poprzedniej wersji, popraw tylko i wyłącznie to co ci powiedziałem i będzie działać. Tylko że się nie spodziewaj że czas wyliczeń chociaż mniej więcej zbliży się do wersji iteracyjnej.

_13th_Dragon napisał(a):

problem masz tu:
gra:=gra(t, ind+b,k-1)
jeżeli funkcja zwróciła true to musisz natychmiast zrobić exit;

Dodać if gra then exit; po tej istrukcji wyżej czy zrobić to tak else if ind=max then begin gra:=true; exit end