Ханойски кули Легендата



Дата25.07.2016
Размер40.1 Kb.
#6563
ТипРешение
Ханойски кули
Легендата

Източни монаси пазели три кули, на които били закачени 64 златни диска. Те били наредени на едната кула по големина, така че върху всеки диск имало по-малък диск. Монасите трябвало да преместят дисковете от първата кула на третата един по един, но без да слагат по-голям диск върху по-малък. Когато 64те диска щели да бъдат преместени, светът щял да свърши.


Играта

Минималният брой ходове е 2n



http://chemeng.p.lodz.pl/zylla/games/hanoi5e.html

http://www.superkids.com/aweb/tools/logic/towers/
Условие на задачата

На една кула са наредени N диска, подредени в намаляващ ред по диаметрите им. Да се преместят дисковете от първата на третата кула, като се използва втората за помощна.


Правилата за преместване са следните:

  • всеки път се мести по 1 диск

  • не може да се сложи диск с по-голям диаметър върху диск с по-малък


Решение

а) псевдокод


б) програма

#include


const unsigned n = 4;
void diskMove(unsigned n, char a, char b)

{ printf("%u %c %c.\n", n, a, b); }


void hanoy(char a, char c, char b, unsigned numb)

{ if (1 == numb)

diskMove(1, a, c);

else {


hanoy(a, b, c, numb - 1);

diskMove(numb, a, c);

hanoy(b, c, a, numb - 1);

}

}


int main(void) {

printf("%u\n", n);

hanoy('A', 'C', 'B', n);

return 0;

}


Обхождане на граф в дълбочина - DFS
а) описание на рекурсивно обхождане на граф в дълбочина с псевдокод

RecursiveDFS(v)

If (v не е посетен)

Отбелязваме v за посетен

For всяко ребро (v, w)

RecursiveDFS(w)



б) с програма




#include

#define MAXN 200

const unsigned n = 14;

const unsigned v = 5;

const char A[MAXN][MAXN] = {

{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},

{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0},

{0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1},

{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},

{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1},

{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0}

};
char used[MAXN];

void DFS(unsigned i)

{ unsigned k;

used[i] = 1;

printf("%u ", i+1);

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

if (A[i][k] && !used[k]) DFS(k);

}

int main(void) {



unsigned k;

for (k = 1; k < n; k++) used[k] = 0;

printf("%u: \n", v);

DFS(v-1);

printf("\n");

return 0;

}


Търсене с връщане назад – backtracking – алгоритми с отстъпване

Основни стъпки


  • Тръгва се от едно частно решение

  • На всяка стъпка се прави опит от текущото решение да се продължи

  • Ако на някоя стъпка се окаже невъзможно да се продължи се извършва връщане назад към предишно частично решение и се прави опит то да се разшири по друг начин


а) лабиринти

http://www.siteexperts.com/tips/functions/ts20/mm.asp

Масивът М от нули и единици, с размерност NxN представя лабиринт от полета, като с единица са кодирани полетата, през които не може да се минава, а с нула – проходимите полета. Движение в лабиринта може да се извършва в съседните хоризонтални или вертикални проходими полета. Променливите M[1,1] и M[N,N] съдържат 0. Да се напише програма, която получава такъв лабиринт и извежда най-краткия път от полето (1,1) до полето (N, N) или съобщение, че няма път през дадения лабиринт.


б) оцветяване на географската карта

Да се напише програма, която оцветява географската карта с минимален брой цветове, така че никои две съседни области да не са оцветени с един и същи цвят.


в) разполагане на n царици върху шахматната дъска nxn

Да се напише програма, която намира всички възможни начини за разполагане на N царици върху шахматната дъска, по такъв начин че никоя царица да не заплашва друга.


г) намиране на път между два града

Дадени са N града и преките пътища между тях. Да се напише програма, която при задаване на два града извежда един възможен път между тях (списък от градовете, които го съставят) или съобщение, че няма такъв.


д) задачи върху мрежа от квадратчета

Дадена е двумерна мрежа от клетки, всяка от които е празна или запълнена. Запълнените клетки, които са свързани, т.е. имат съседни в хоризонтално, вертикално или диагонално направление, образуват област. Да се напише програма, която намира броя на областите и размерът ( в брой клетки) на всяка област.

Генериране на пермутации с рекурсивни алгоритми


  1. Генериране на пермутации с вмъкване на n-ти елемент на всяко възможно място в пермутация от n-1 елемента

Пример


1


12

21


312

132


123
321

231


213


Без рекурсия 

На ANSI C++, с използване на стандартната библиотека с алгоритми и структури от данни (STL)




#include

#include


int main ( )

{
char v[ ] = "abcd";


do {

cout << v << endl;

} while (next_permutation( v, v + 4));
system("pause");

return 0;

}




На С с рекурсия


#include
#define MAXN 100
const unsigned n = 5;
unsigned a[MAXN];
void print(void)

{ unsigned i;

for (i = 0; i < n; i++) printf("%u ", a[i] + 1);

printf("\n");

}
void permut(unsigned k)

{ unsigned i, swap;

if (k == 0) print();

else {


permut(k - 1);

for (i = 0; i < k - 1; i++) {

swap = a[i]; a[i] = a[k-1]; a[k-1] = swap;

permut(k - 1);

swap = a[i]; a[i] = a[k-1]; a[k-1] = swap;

}

}



}
int main(void) {

unsigned i;

for (i = 0; i < n; i++) a[i] = i;

permut(n);

system("pause");

return 0;



}









Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница