Hanoi - plus

题目描述

如果将课本上的汉诺塔问题稍做修改：给定 N 只盘子，3 根柱子，但是允许每次最多移动相邻的 M 只盘子（当然移动盘子的数目也可以小于 M）, 最少需要多少次？

输入格式

输入数据仅有一行，包括两个数 N 和 M（0<=M<=N<=8）

输出格式

仅输出一个数，表示需要移动的最少次数

样例输入

 5    2

样例输出

7

代码

#include <iostream>
using namespace std;
int count=0;    //公有定义

void cs(char A,int N,char C)
{
count++;
}

void hannota(int N,char A,char B,char C)
{
if(N==1)
{
cs(A,1,C);
}

if(N!=1)
{
hannota(N-1,A,C,B);
cs(A,N,C);
hannota(N-1,B,A,C);
}
}

int main( )
{
int N,M;
char A,B,C;
cin>>N>>M;

if(N%M==0)                             //将N个盘分成N/M份
{
N=N/M;
}

if(N%M!=0)                             //多出来的算作一个盘
{
N=N/M;
N++;
}
hannota(N,'A','B','C');
cout<<count;
return 0;
}

//与典型汉诺塔相比，相邻M盘条件不同，所以将M盘看作整体

//其实是 hanoi