漢諾塔問題
題目來源：C語言程式設計（第四版）譚浩強
例7.8 古代有一個梵塔，塔內有三個座A，B，C，開始時A座上有64個盤子，盤子大小不等，大的在下，小的在上，將這64個盤子從A座移到C座，但規定每次只允許移動一個盤，且在移動程序中在3個座上都始終保持大盤在下，小盤在上，要求編程輸出移動盤子的步驟，
#include<stdio.h>
//輸入盤子個數，輸出移動次數
int Hanoi(int n)
{
if (n - 1 > 1)
{
return 1 + 2 * Hanoi(n - 1);//Hanoi（n-1）的含義是第一步將n-1個盤子移動到另外一根柱子上
//+1代表第二步將剩余的一個最大的盤子移動到一個座上
//*2代表需要將n-1個盤子移動兩次，也就是第三步將n-1個盤子移動到最大的盤子上
}
else
{
return 3;//將位于同一個座上的兩個盤子移動到另外一個座上需要三步
}
}
int main()
{
int n = 0;
scanf("%d", &n);
long long ret = Hanoi(n);
printf("%lld\n", n);
}
現在實作進階：將每一步的具體移動操作都列印出來，
void move(char x,char y)
{
printf("%c->%c\n", x, y);
}
void hanoi(int n, char one, char two, char three)
{
if (1 == n)
{
move(one, three);
}
else
{
//這里的后三個引數不必刻意去記憶
//只需要畫上一個帶有三個盤子的漢諾塔模型
//對三個柱子分別標上A，B，C
//需要移動的兩個盤子所在的柱子標記上resource（源頭），即對應one
//對需要將兩個盤子最終所放置的柱子標記上destination（目的地），即對應three
//對剩下的一根柱子標記上tmp（中間變數），即對應two
//引數傳遞順序就是按照A，B，C所對應的英文數字
hanoi(n - 1, one, three, two);
move(one, three);
hanoi(n - 1, two, one, three);
}
}
int main()
{
int m = 0;
scanf("%d", &m);
hanoi(m, 'A', 'B', 'C');
return 0;
}
青蛙跳臺階
題目來源：《劍指 Offer》
一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上一個 n 級的臺階總共有多少種跳法，
當n>2時，此時我們可以把n級臺階的跳法看成是n的函式:f(n)；如果青蛙第一步跳一級臺階，之后的跳法數目就是之后剩余n-1級臺階的跳法數目，即f(n-1)；另一種可能的情況就是青蛙第一步跳兩級臺階，之后的跳法數目就是之后剩余的n-2級臺階的跳法數目；所以n級臺階的不同跳法的總數是f(n)=f(n-1)+f(n-2)
這樣就可以和斐波那契數列建立起聯系了！
int Jump(int n)
{
if (n > 2)
{
return Jump(n - 1) + Jump(n - 2);//第一次跳一梯的和第一次跳兩梯的情況
}
else if(n==2)//還剩兩梯的時候易知有兩種跳法
{
return 2;
}
else//還剩一梯的時候易知有一種跳法
{
return 1;
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Jump(n);
printf("%d\n", ret);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/278904.html
標籤：其他
下一篇：1.嵌入式學習路線和方法