fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <math.h>
  5. #include <time.h>
  6.  
  7. unsigned int n; // liczba krazkow
  8. unsigned int rods; // liczba drazkow
  9. unsigned int moves; // liczba przelozen
  10.  
  11. /**
  12.  * Zmienne liczace czas
  13.  */
  14. clock_t start;
  15. clock_t end;
  16.  
  17. /**
  18.  * Jeden element - jeden drazek
  19.  *
  20.  * Tablica *disks zawiera krazki znajdujace sie aktualnie na drazku wg. wzoru:
  21.  *
  22.  *     {1, 2, 3, 4} - drazek zawiera 4 dane krazki
  23.  *     {0, 0, 0, 0, 0} - drazek nie zawiera krazkow
  24.  *     {1, 3, 5, 0, 0} - drazek zawiera krazki 1, 3 i 5
  25.  */
  26. typedef struct rod {
  27.     int num;
  28. 	int *disks;
  29. 	rod *next;
  30. 	rod *prev;
  31. } rod;
  32.  
  33. void init(rod**, rod**);
  34. void add_rod(rod**, rod**);
  35. void hanoi(rod**, rod**);
  36. void unshift(int, int**);
  37. void pop(int**);
  38. void wyswietl_ulozenie(rod*);
  39. void wyswietl_statystyki();
  40. void time_start();
  41. void time_stop();
  42. double execution_time();
  43.  
  44. int main()
  45. {
  46. 	rod *head = NULL, *tail = NULL;
  47.  
  48. 	printf("Podaj liczbe krazkow: ");
  49. 	scanf("%u", &n);
  50.  
  51. 	printf("Podaj liczbe drazkow: ");
  52. 	scanf("%u", &rods);
  53.  
  54. 	if(rods == 0)
  55. 	{
  56. 		printf("Zbyt malo drazkow!");
  57. 		exit(EXIT_FAILURE);
  58. 	}
  59.  
  60. 	init(&head, &tail);
  61.  
  62. 	printf("\nInput:\n\n");
  63. 	wyswietl_ulozenie(head);
  64.  
  65. 	// Przekladaj krazki
  66. 	hanoi(&head, &tail);
  67.  
  68. 	printf("\nOutput:\n\n");
  69. 	wyswietl_ulozenie(head);
  70.  
  71. 	wyswietl_statystyki();
  72.  
  73. 	fflush(stdin);
  74. 	getchar();
  75.  
  76. 	return 0;
  77. }
  78.  
  79. /**
  80.  * Inicjuj dzialanie programu - kaz utworzyc drazki
  81.  * 
  82.  * @param **head
  83.  * @param **tail
  84.  */
  85. void init(rod **head, rod **tail)
  86. {
  87. 	for(int i = 0; i < (int)rods; i++)
  88. 	{
  89. 		add_rod(head, tail);
  90. 	}
  91. }
  92.  
  93. /**
  94.  * Dodaj nowy element listy bedacy drazkiem
  95.  * 
  96.  * @param **head
  97.  * @param **tail
  98.  */
  99. void add_rod(rod **head, rod **tail)
  100. {
  101. 	rod *temp;
  102. 	int count = 1;
  103.  
  104. 	if(*head == NULL)
  105. 	{
  106. 		*head = (rod*) malloc(sizeof(rod));
  107.  
  108. 		(*head)->disks = (int*) malloc(sizeof(int)*(n - 1));
  109. 		for(int i = 0; i < (int)n; i++)
  110. 		{
  111. 			(*head)->disks[i] = i + 1;
  112. 		}
  113.  
  114. 		(*head)->num = count;
  115. 		(*head)->next = (*head)->prev = NULL;
  116.  
  117. 		*tail = *head;
  118. 	}
  119. 	else
  120. 	{
  121. 		temp = *head;
  122.  
  123. 		while(temp->next != NULL)
  124. 		{
  125. 			count++;
  126. 			temp = temp->next;
  127. 		}
  128.  
  129. 		temp->next = (rod*) malloc(sizeof(rod));
  130. 		temp->next->prev = temp;
  131. 		temp = temp->next;
  132. 		temp->num = count + 1;
  133.  
  134. 		temp->disks = (int*) malloc(sizeof(int)*(n - 1));
  135. 		for(int i = 0; i < n; i++)
  136. 		{
  137. 			temp->disks[i] = 0;
  138. 		}
  139.  
  140. 		temp->next = NULL;
  141.  
  142. 		if(temp->num <= 3) // divide and conquere w przypadku n > 3 drazkow
  143. 		{
  144. 			*tail = temp;
  145. 		}
  146. 	}
  147. }
  148.  
  149. /**
  150.  * Algorytm przekladajacy krazki wg. nastepujacego sposobu:
  151.  *
  152.  *   1. Jesli ilosc krazkow jest parzysta, przesuj najmniejszy element w prawo,
  153.  *      jestli nieparzysta przesuj w lewo
  154.  *   2. Wykonaj pierwszy mozliwy ruch bez wykorzystywania najmniejszego krazka
  155.  *   3. Powtarzaj punkty 1 i 2 az do uzyskania poprawnego wyniku
  156.  *
  157.  * Więcej drążków to już kwestia powtarzania algorytmu rods - 2 razy (rods - liczba drążków),
  158.  * w tym celu *head i *tail przesuwane są co 1 pole w prawo przy każdym powtórzeniu.
  159.  * 
  160.  * @param **head
  161.  * @param **tail
  162.  */
  163. void hanoi(rod **head, rod **tail)
  164. {
  165. 	// Zaczynamy liczyc czas
  166. 	time_start();
  167.  
  168. 	rod *temp, *temp2, *head_t = *head;
  169. 	int flag = 0, div = 0;
  170.  
  171. 	for(int i = 0; i < rods - 2; i++)
  172. 	{
  173. 		while((*tail)->disks[n - 1] != n)
  174. 		{
  175. 			temp = *head, flag = 0;
  176.  
  177. 			if(div % 2 == 0) // move smallest disk to the right if odd, or left if even
  178. 			{
  179. 				while(temp != (*tail)->next)
  180. 				{
  181. 					if(flag == 1)
  182. 					{
  183. 						unshift(1, &temp->disks);
  184. 						break;
  185. 					}
  186. 					if(temp->disks[0] == 1)
  187. 					{
  188. 						pop(&temp->disks);
  189. 						flag = 1;
  190. 					}
  191.  
  192. 					if(n % 2 == 0)
  193. 					{
  194. 						temp = (temp->next == (*tail)->next) ? *head : temp->next;
  195. 					}
  196. 					else
  197. 					{
  198. 						temp = (temp->prev == (*head)->prev) ? *tail : temp->prev;
  199. 					}
  200. 				}
  201. 			}
  202. 			else // make first possible move
  203. 			{
  204. 				while(temp != (*tail)->next && flag == 0)
  205. 				{
  206. 					temp2 = *head;
  207. 					while(temp2 != (*tail)->next)
  208. 					{
  209. 						if((temp->disks[0] < temp2->disks[0] || temp2->disks[0] == 0) && temp->disks[0] != 1 && temp->disks[0] != 0 && temp->num != temp2->num)
  210. 						{
  211. 							int t = temp->disks[0];
  212. 							pop(&temp->disks);
  213. 							unshift(t, &temp2->disks);
  214. 							flag = 1;
  215. 							break;
  216. 						}
  217.  
  218. 						temp2 = temp2->next;
  219. 					}
  220.  
  221. 					temp = temp->next;
  222. 				}
  223. 			}
  224.  
  225. 			div++, moves++;
  226. 		}
  227.  
  228. 		// divide and conquer
  229. 		if(i < rods - 3)
  230. 		{
  231. 			if((*head)->num <= i + 1)
  232. 				*head = (*head)->next;
  233. 			if((*tail)->num <= i + 3)
  234. 				*tail = (*tail)->next;
  235. 		}
  236. 	}
  237.  
  238. 	*head = head_t;
  239.  
  240. 	// Algorytm zakonczony
  241. 	time_stop();
  242. }
  243.  
  244. /**
  245.  * Powieksza tablice o jeden element - dodaje go na poczatek tablicy, a 
  246.  * wszystkie poprzednie elementy przesuwa o 1 indeks w prawo
  247.  *
  248.  * @param el Element do wstawienia na poczatek tablicy
  249.  * @param **arr
  250.  */
  251. void unshift(int el, int **arr)
  252. {
  253. 	for(int i = (int)n - 1; i > 0; i--)
  254. 	{
  255. 		(*arr)[i] = (*arr)[i - 1];
  256. 	}
  257.     (*arr)[0] = el;
  258. }
  259.  
  260. /**
  261.  * Usuwa pierwszy element z tablicy i przesywa jej pozostale elementy
  262.  * o jeden indeks w lewo
  263.  *
  264.  * @param **arr
  265.  */
  266. void pop(int **arr)
  267. {
  268. 	for(int i = 0; i < (int)n - 1; i++)
  269. 	{
  270. 		(*arr)[i] = (*arr)[i + 1];
  271. 	}	
  272. 	(*arr)[n - 1] = 0;
  273. }
  274.  
  275. /**
  276.  * Wyswietla ulozenie krazkow formatowane jako macierz
  277.  *
  278.  * @param *head
  279.  */
  280. void wyswietl_ulozenie(rod *head)
  281. {
  282. 	rod *temp = head;
  283.  
  284. 	for(int i = 0; i < (int)rods; i++)
  285. 	{
  286. 		printf("Drazek %-2d: ", i + 1);
  287. 		for(int j = 0; j < (int)n; j++)
  288. 		{
  289. 			printf("%-3d", temp->disks[j]);
  290. 		}
  291. 		printf("\n");
  292. 		temp = temp->next;
  293. 	}
  294. }
  295.  
  296. /**
  297.  * Wyswietla statystyki wykonywanego algorytmu
  298.  */
  299. void wyswietl_statystyki()
  300. {
  301. 	printf("\n\nIlosc wykonanych przelozen: %u", moves);
  302. 	if(execution_time() == (double)0)
  303. 	{
  304. 		printf("\nCzas wykonania algorytmu jest bliski 0ms");
  305. 	}
  306. 	else
  307. 	{
  308. 		printf("\nCzas wykonania algorytmu: %lfms", execution_time());
  309. 	}
  310. }
  311.  
  312. /**
  313.  * Start counting time
  314.  */
  315. void time_start()
  316. {
  317. 	start = clock();
  318. }
  319.  
  320. /**
  321.  * Finish counting
  322.  */
  323. void time_stop()
  324. {
  325. 	end = clock();
  326. }
  327.  
  328. /**
  329.  * Return time passed
  330.  */
  331. double execution_time()
  332. {
  333. 	return (double)end - start;
  334. }
  335.  
Runtime error #stdin #stdout 0s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Podaj liczbe krazkow: Podaj liczbe drazkow: Zbyt malo drazkow!
https://ideone.com/Jwt4nN
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!