Премини към съдържанието

Препоръчан отговор


Здравейте, имам няколко въпроса относно тези задачи, които се опитвам да реша чрез рекурсия.

Условието на първа задача е :

Дадени са n града (ние въвеждаме бройката) и матрица A ( nxn) . Ако Aji e едно, това означава, че между градовете j и I има пряк път и тогава Aij също ще е 1. Ако Aji е 0, тогава между градовете няма да има пряк път и следователно Aij също ще е 0.

Искам да напиша програма, която намира дали съществува път от град x до град y (може да е недиректен пътя- например от 1 до 2 има директен път и от 2 до 3 също има директен път, но ако от 1 до 3 няма директен път, то програмата ще ми изведе 1, защото от 1 можем да отидем до 2, а от там до 3).

Декларирал съм n и y като глобални променливи, за не тъпча рекурсивната програмата с формални променливи.

Аз пробвам с града като въвеждам все едно матрицата:

1 1 0

1 1 1

0 1 1

И ми изкарва, грешка ( май, че при работата с масива)

Та ще се радвам, ако някой ми каже къде ми е грешката.

// zadacha 1#include <iostream>using namespace std;int n, y;int a[20][20];bool existway(int x, int y){		if (a[x][y] == 1) return 1;	a[x][y] = 0;	a[y][x] = 0;	for ( int p = 0 ; p <= n-1 ; p ++)		if ( a[x][p] == 1) return existway ( p,y);	return 0;	}int main(){	int x; 	cout << "Vuvedete broq na gradovete : "; 	cin >> n;	//Vuvejdane na masiva	for ( int i =0 ; i <= n-1; i++)		for (int j = 0; j <= n-1 ; j++)		{			cout << "Vuvedete a[ " << i << " ][ " << j << " ] : ";			cin >> a[i][j];		}	cout << "Vuvedete  nachalniq i krainiq grad: ";	cin >> x >> y;	if ( existway(x , y)) cout << "Ima put "  << endl;	else cout << "Nqma put "<< endl;	cin.sync();	cin.get();	return 0;}
Ето я и втората програма с условие:

Квадратна мрежа с k реда и k стълба (1 ≤ k ≤ 20) има два вида квадратчета - бели и черни. В черно квадратче може да се влезе, но не може да се излезе. От бяло квадратче може да се премине във всяко от осемте му съседни, като се прекоси общата им страна или връх. Да се напише програма, която ако са дадени произволна мрежа с бели и черни квадратчета и две произволни квадратчета - начално и крайно, определя дали от началното квадратче може да се премине в крайното.

#include <iostream>

using namespace std;

int m,p , n;

int a[20][20]; // bool ne moje da se vuvejda s cin !!! predpolagam

bool way( int x , int y)

{

if ( a[x][y] == 0 ) return 0;

if ( x == m && y == p ) return 1;

if ( x < 0 || x > n-1 || y < 0 || y > n-1 ) return 0;

a[x][y] = 0;

bool b = way ( x-1 , y-1 ) || way ( x , y-1 ) || way (x+1 , y-1 ) ||

way ( x-1 , y ) || way( x+1,y) ||

way(x-1,y+1) || way(x,y+1) || way(x+1,y+1) ;

a[x][y] = 1;

return b;

}

int main()

{

int n , x , y;

cout << "Vuvedete broqt na kvadratchetata na red ";

cin >> n;

cout << "Vuvedete koordinatite na nachalnata tochka : ";

cin >> m >> p;

cout << "Vuvedete koordinatite na krainata tochka : ";

cin >> x >> y;

for (int i = 0; i <= n-1; i++)

for(int j = 0; j <= n-1 ; j++)

{

cout << "Vuvedete a[ " << i << " ][ " << j <<" ] : ";

cin >> a[j];

}

if( way(x,y)) cout << "Ima put " << endl;

else cout << "Nqma put " << endl;

cin.sync();

cin.get();

return 0;

}

Пробвах и подобна програма само, че с рекурсивна функция:

bool way( int x , int y){	if ( a[x][y] == 0 ) return 0; 	if ( x == m && y == p ) return 1;	if ( x < 0 || x > n-1 || y < 0 || y > n-1 ) return 0;	a[x][y] = 0;	return	 way ( x-1 , y-1 ) || way ( x , y-1 ) || way (x+1 , y-1 ) || 			 way ( x-1 , y )            ||           way( x+1,y) ||			 way(x-1,y+1)	||	  way(x,y+1)  ||	 way(x+1,y+1) ;	}
Разликата между двете е , че при първата (ако не се лъжа) се запазва матрицата в началния си вид, докато при втората програма някои (или всички) 1-ци ще станат 0-ли.

Обаче като пробвам матрицата

1 0 0

0 1 0

0 0 1

И ми изкарва, че няма такъв път, а очевидно този по диагонала ни върши работа.

Също така имам въпрос съответно след като получа отговор на горепосочените проблеми:

Могат ли тези случаи да се направят с цикъл в програмата, а не с рекурсивна функция?

Благодаря предварително.

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Всъщност си открих грешката в задачата с черните и белите квадратчета и тя е, че съм декларал n и като глобална и като локална променлива в int main(). Като оставим n да ни е глобална променлива работи като хората. Ще се радвам, ако някой вкара едно рамо за другата с градовете :)

Редактирано от rusrusrus (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Ще се радвам, ако някой вкара едно рамо за другата с градовете :)

Удряме де :) Ще пробвам на сухо, че нямам компилатор под ръка.

Значи, когато ползваш рекурсия е изключително важно, да поставиш правилно и проверено условие за край, т.е. рекурсията абсолютно винаги да свършва. Нека разгледаме твоята функция заедно със примерната матрица, която си задал.

[*]Да кажем че въведем запитване за път между град 0 и 2.

[*]функцията ти проверява директната връзка - няма такава.

[*]след това ти нулираш двете клетки от масива - странна работа, едната така или иначе не е 1, а другата трябва да е такава по условие - не е работа на тази функция да се прави на коректор на входните данни. Но това, само по себе си, не е проблем.

[*]Виж цикълът е сериозен проблем. Обикаляш всички градове отново. Всички. А си в рекурсия. Тоест заради този цикъл може да започнеш съвсем отначало. Точно така и става - гледай:

[*]цикълът почва.

[*]проверяваме за връзка между град 0 и първия град - който е 0 - има. Проверяваме за връзка между град 0 и втория град - който е 2. Опа. Ама ние не влязохме ли точно в този случай преди малко? Ето ти го безкрайният цикъл.

Трябва ти друг подход. И тук идва:

Декларирал съм n и y като глобални променливи, за не тъпча рекурсивната програмата с формални променливи.

Стига де... Тя (рекурсивната функция) не е жена, че да се оплаква от много ядене. Не зная, как са ви учили, но глобални променливи се ползват само в много конкретни и специфични случаи и този не е един от тях. Ако добавиш някой и друг параметър, с които да покажеш докъде си стигнал, ще ти се реши проблема.

 

Могат ли тези случаи да се направят с цикъл в програмата, а не с рекурсивна функция?

Благодаря предварително.

Да може. Даже по принцип е хубаво да избягваш рекурсията (говорим за C или C++) освен ако: а) ще ти направи кода по-четлив или прост и б) знаеш, колко е максималната дълбочина на рекурсията и си проверил, че работи с нея. Редактирано от flare (преглед на промените)
  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

А може ли примерно решение с цикъл и с рекурсия ( оптимално) . Иначе и аз открих това за зациклянето и се надявам да мога да го оправя.Относно глобалните променливи в книгата има такива примери и аз си чета от нея, в университета сме още в началото.Относно рекурсията знам, че е хубаво да се избягва в C++. Обаче искам да мога да пиша тези програми и само чрез цикли и чрез рекурсия, защото тази рекурсия по-нататък ще ми трябва в друг език примерно и какво ще стане - уж съм чувал за рекурсия и най-сложното, което мога да направя с нея е да намеря някакъв биномен коефициент или да напиша рекурсивна функция, с която намираме някакъв си факториел.Пак казвам, знам че са бавни рекурсивните програми (поне в C++), но не искам този "рекурсивен" начин на мислене да го уча след 1 година.Тези програми като цяло искат доста повече мислене, от тези които съм виждал до сега и за това се старая да не ги избягвам и да не се страхувам от тях :) .Аз ще се опитам да ги измисля с цикли и съответно да оправя сегашната рекурсия на едната.Благодаря много за бързия отговор.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

А може ли примерно решение с цикъл и с рекурсия ( оптимално) .

Ми трябва да изнамеря някакъв компилатор :). Но ти не ми изглеждаш, като да те мързи, в нета има реализации и може да си намериш по-бързо.  

Пак казвам, знам че са бавни рекурсивните програми (поне в C++)

Не ме разбра тук. Скоростта не е главното, което трябва да вземеш предвид. Проблемът на рекурсията е в самата имплементация в езика. При всяко извикване на функция, процесорът запазва част от регистрите си в стека. Аргументите на функцията отиват в стека. Локалните променливи на функцията и те. Когато излезеш от функцията тези неща се освобождават. Обаче при рекурсия, функцията извиква себе си много пъти вложено, при което необходимата памет нараства много. Стекът, за разлика от динамично заделяната памет обикновено е с фиксиран и (относително) малък размер. Съответно може да свърши. Затова казах че е много важно да знаеш колко е дълбочината на рекурсията в най-лошия случай, в който може да изпадне програмата ти. Итеративните решения (т.е. с цикъл) нямат този проблем и работят за произволен брой повторения. Има езици (а и някои компилатори на C и C++ също) които правят така наречената tail recursion optimization, които директно си превръщат посоченият вид рекурсия в цикъл, премахвайки описания проблем. И точно защото в случая е само пожелателно, казвам "да внимаваш когато", а не "да не" я ползваш.


Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Ще може ли да ми напишете цикъла, ако не ви е проблем, защото в интернет не намирам как мога да заменя рекурсията с цикъл.И също така, ако може малко по-подробно тази идея с тази променлива, която да брои до къде съм стигнал? Питах няколко човека, ама всеки или ми вика, че всяка рекурсия може да се замени с цикъл и не ми показва как става или пък ми викат, че трябвало някакви стекове и не знам си какво и работата ставала долу-горе същата като с рекурсия.

Искам докато съм на този урок да ми стане ясно как трябва да действам на практика с такъв тип задачи. Благодаря, предварително.

Редактирано от rusrusrus (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.