河内塔 (Frame Stewart) k 钉在 c
Tower of Hanoi (Frame Stewart) k pegs in c
Frame Stewart算法有没有C语言的实现。我在 python 中有以下代码可以正常工作。
def FrameStewart(ndisks,npegs):
if ndisks ==0: #zero disks require zero moves
return 0
if ndisks == 1 and npegs > 1: #if there is only 1 disk it will only take one move
return 1
if npegs == 3:#3 pegs is well defined optimal solution of 2^n-1
return 2**ndisks - 1
if npegs >= 3 and ndisks > 0:
potential_solutions = (2*FrameStewart(kdisks,npegs) + FrameStewart(ndisks-kdisks,npegs-1) for kdisks in range(1,ndisks))
return min(potential_solutions) #the best solution
#all other cases where there is no solution (namely one peg, or 2 pegs and more than 1 disk)
return float("inf")
a = int(raw_input("Disks [>] "))
b = int(raw_input("rods [>] "))
print FrameStewart(a, b) #prints 161
我写了下面的 C 代码,但没有给出正确的输出
#include<stdio.h>
int power(int a, int b){
int p=1,i;
for(i=0;i<b;i++){
p*=a;
}
return p;
}
int min(int abc[],int n){
int min = abc[0],i;
for(i=1;i<n;i++)
{
if(abc[i]<min){
min = abc[i];
}
}
return min;
}
int hanoi(int rods, int disks)
{
int moves=2147483647,i;
if(disks==0)
return 0;
if(disks==1)
return 1;
if(rods==3)
return power(2,disks)-1;
if(rods>=3 && disks>0){
int potential_moves[disks-1];
for(i=1;i<disks;i++){
potential_moves[i-1]=2*hanoi(i,rods) + hanoi(disks-i,rods-1);
}
return min(potential_moves, disks-1);
}
return moves;
}
int main(){
int rods,disks;
printf("***** Tower of Hanoi (for n rods) *****\n");
printf("Enter no. of disks : ");
scanf("%d",&disks);
printf("Enter no. of rods : ");
scanf("%d",&rods);
if(disks>1 && rods<3){
printf("Invalid input rods must be greater than 2 for 2 or more disks\n");
return -1;
}
int moves = hanoi(rods, disks);
printf("Minimum np. of moves are : %d\n", moves);
return 0;
}
谁能告诉我为什么我的代码不正确或 Frame Stewart 算法在 C 中的正确实现。
你的逻辑是正确的,但有一个简单但难以发现的错误。您在递归调用函数时反转了参数。
看这里
potential_moves[i-1]=2*hanoi(i,rods) + hanoi(disks-i,rods-1);
该行应该是
potential_moves[i-1]=2*hanoi(rods,i) + hanoi(rods-1, disks-i);
问题解决了!
Frame Stewart算法有没有C语言的实现。我在 python 中有以下代码可以正常工作。
def FrameStewart(ndisks,npegs):
if ndisks ==0: #zero disks require zero moves
return 0
if ndisks == 1 and npegs > 1: #if there is only 1 disk it will only take one move
return 1
if npegs == 3:#3 pegs is well defined optimal solution of 2^n-1
return 2**ndisks - 1
if npegs >= 3 and ndisks > 0:
potential_solutions = (2*FrameStewart(kdisks,npegs) + FrameStewart(ndisks-kdisks,npegs-1) for kdisks in range(1,ndisks))
return min(potential_solutions) #the best solution
#all other cases where there is no solution (namely one peg, or 2 pegs and more than 1 disk)
return float("inf")
a = int(raw_input("Disks [>] "))
b = int(raw_input("rods [>] "))
print FrameStewart(a, b) #prints 161
我写了下面的 C 代码,但没有给出正确的输出
#include<stdio.h>
int power(int a, int b){
int p=1,i;
for(i=0;i<b;i++){
p*=a;
}
return p;
}
int min(int abc[],int n){
int min = abc[0],i;
for(i=1;i<n;i++)
{
if(abc[i]<min){
min = abc[i];
}
}
return min;
}
int hanoi(int rods, int disks)
{
int moves=2147483647,i;
if(disks==0)
return 0;
if(disks==1)
return 1;
if(rods==3)
return power(2,disks)-1;
if(rods>=3 && disks>0){
int potential_moves[disks-1];
for(i=1;i<disks;i++){
potential_moves[i-1]=2*hanoi(i,rods) + hanoi(disks-i,rods-1);
}
return min(potential_moves, disks-1);
}
return moves;
}
int main(){
int rods,disks;
printf("***** Tower of Hanoi (for n rods) *****\n");
printf("Enter no. of disks : ");
scanf("%d",&disks);
printf("Enter no. of rods : ");
scanf("%d",&rods);
if(disks>1 && rods<3){
printf("Invalid input rods must be greater than 2 for 2 or more disks\n");
return -1;
}
int moves = hanoi(rods, disks);
printf("Minimum np. of moves are : %d\n", moves);
return 0;
}
谁能告诉我为什么我的代码不正确或 Frame Stewart 算法在 C 中的正确实现。
你的逻辑是正确的,但有一个简单但难以发现的错误。您在递归调用函数时反转了参数。 看这里
potential_moves[i-1]=2*hanoi(i,rods) + hanoi(disks-i,rods-1);
该行应该是
potential_moves[i-1]=2*hanoi(rods,i) + hanoi(rods-1, disks-i);
问题解决了!