Дастурлашни ўҚитиш муаммолари: рекурсияни массивларга татбиқ Қилиш

Масаланинг энг содда ечими қуйидагича:

Масаланинг энг содда ечими қуйидагича:

• Йўловчи турган бошланғич катак A[i,j] га 2 сони ёзилади ва k=2 деймиз. А лабиринтнинг барча катакларини қараймиз. Уларнинг бирортасида 0 ёзилган бўлиб, унинг тўртта қўшни катакларидан бирида k (у ҳозирча 2 га тенг) турган бўлса, А нинг қаралаётган катагига k+1 сони ёзилади. Энди k нинг қийматини оширамиз катаклардан бирига k сони ёзилганда тугайди. Массивни кўриб чиқ: k:=k+1 ва А лабиринтнинг катакларини яна бир марта текширамиз. Жараён чегаравий ишлар сони энг қисқа йўлдаги катаклар сонига тенг бўлади.
• Содда қилиб айтганда, бошланғич катакка дастлаб 2 сони ёзилади. Унинг нолли қўшни катагини излаймиз ва унга 3 ни ёзамиз. Энди 4 сонини ёзиш учун 3 ёзилган катакнинг ноль ёзилган қўшни катагини қидирамиз ва ҳ.к. Ушбу жараён чегравий катакка k сонини (k≥2) ёзилганда ёки йўл мавжуд бўлмаганда (боши берк вазиятга тушиб қолганда) тугайди.
• Боши берк вазият (2 сони ёзилган катакнинг нолли қўшнилари қолмаганда) юзага келади. Агар боши берк катакка k>2 сони ёзилган бўлса, унга 1 сони ёзилади ва унинг k-1 сони турган кўшни катагига ўтилади.

Бу масаланинг дастурини рекурсив усулда қуйидагича ёзилади.

Бу масаланинг дастурини рекурсив усулда қуйидагича ёзилади.

• Program labirint;
• Const m=40; n=40;
• Var i, j: integer;
• natija: boolean;
• A: array [1..m, 1..n] of byte.
• Procedure L (i, j: integer);
• begin
• if not(natija) then
• if a[i, j]=0 then begin
• if (i=1) or (i=m) or (j=1) or (j=m) then natija:=true;
• A[i, j]:=1; L(i, j-1); L(i, j+1); L(i-1, j); L(i+1, j);
• If natija then write (i, ‘ ‘, j, ‘<-’)
• end;
• end;
• Begin
• For i:=1 to m do begin
• For j:=1 to n do Readln (a[i,j]); Readln;
• end;
• Write(‘i, j:=’); Readln(i, j);
• writeln;
• natija:= false;
• L(i,j);
• If not(natija) then writeln(‘Chiqish yoli mavyud emas’)
• End.