?

問(wèn)題描述

一個(gè)環(huán)上有10個(gè)點(diǎn)，編號(hào)為0-9，從0點(diǎn)出發(fā)，每步可以順時(shí)針到下一個(gè)點(diǎn)，也可以逆時(shí)針到上一個(gè)點(diǎn)，求：經(jīng)過(guò)n步又

回到0點(diǎn)有多少種不同的走法

舉例:

如果n=1，則從0出發(fā)只能到1或者9，不可能回到0，共0種走法如果n=2，則從0出發(fā)有4條路徑:0->1->2, 0->1->0, 0->9->8, 0->9->0,其中有兩條回到了0點(diǎn)，故一共有2種走法

• ?

思路(動(dòng)態(tài)規(guī)劃)

• 我們可以想到，再回到0點(diǎn)可以從右面回來(lái)，也可以從左面回來(lái)，即先到達(dá)旁邊的一個(gè)點(diǎn)，看看有多少回來(lái)的方法

即可。所以運(yùn)用動(dòng)態(tài)規(guī)劃的思想，我們可以寫(xiě)出遞推式如下：

d(k, j) = d(k-1, j-1) + d(k-1, j+1);

• d(k, j)表示從點(diǎn)j 走k步到達(dá)原點(diǎn)0的方法數(shù)，因此可以轉(zhuǎn)化為他相鄰的點(diǎn)經(jīng)過(guò)k-1步回到原點(diǎn)的問(wèn)題，這樣將問(wèn)題的規(guī)模

縮小.由于是環(huán)的問(wèn)題， j-1, j+1可能會(huì)超出 0到n-1的范圍，因此，我們將遞推式改成如下：

d(k, j) = d(k-1, (j-1+n)%n) + d(k-1, (j+1)%n);

• 因?yàn)閱?wèn)題從走k步轉(zhuǎn)化為走k-1步的問(wèn)題，所以在寫(xiě)程序的時(shí)候我們就按照k從0開(kāi)始遞增的循環(huán)寫(xiě)，這樣當(dāng)計(jì)算第k步的

時(shí)候可以直接使用k-1步的結(jié)果。

go實(shí)現(xiàn)

//n 代表點(diǎn)的個(gè)數(shù),k代表bushu func GetSteps(n int, k int) int {if n == 0 {return 1}if n == 2 {if n%2 == 0 {return 1} else {return 0}}var dp [100][100]intdp[0][0] = 1for i := 1; i < n; i++ {dp[0][i] = 0}for j := 1; j <= k; j++ {for i := 0; i < n; i++ {dp[j][i] = dp[j-1][(i-1+n)%n] + dp[j-1][(i+1)%n]}}return dp[k][0] }

C++實(shí)現(xiàn)

/**
?* 一個(gè)圓環(huán)， 有n個(gè)點(diǎn)， 從0出發(fā)，每次只能走一步，問(wèn)走k步，有多少種方法可以走回來(lái)
?*/
?
#define N 100
?
int get_step_num(int n, int k)
{
?? ?if (n==1){
?? ??? ?return 1;
?? ?}
?
?? ?if (n==2){
?? ??? ?if (k%2==0)
?? ??? ??? ?return 1;
?? ??? ?else?
?? ??? ??? ?return 0;
?? ?}
?
?? ?int arr[2][N] = {0};
?? ?int flag = 1, i = 0, j = 0;
?
?? ?arr[0][0] = 1;
?? ?for (i=1; i<n; i++) {
?? ??? ?arr[0][i] = 0;
?? ?}
?
?? ?// j is the current step
?? ?for (j=1; j<=k; j++) {
?? ??? ?for (i=0; i<n; i++) {
?? ??? ??? ?arr[flag][i] = arr[!flag][(i-1+n)%n] + arr[!flag][(i+1)%n];
?? ??? ?}
?? ??? ?flag = !flag;
?? ?}
?? ?
?? ?return arr[!flag][0];
}
?
int main()
{
?? ?int n, k;
?? ?printf("Please input the number n and the step k:\n");
?? ?scanf("%d%d", &n, &k);
?
?? ?printf("%d\n", get_step_num(n, k));
?
?? ?return 0;
}

?

總結(jié)

以上是生活随笔為你收集整理的圆环回原点问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。