#汉诺塔问题
简介
汉诺塔是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
- 每次只能移动一个圆盘；
- 大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
##解法 解法的基本思想是递归。假设有A、B、C三个塔，A塔有N块盘，目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的N-1块盘移到C。
每次移动多于一块盘时，则再次使用上述算法来移动。
递归代码
//
// main.cpp
// hannoi
//
// Created by moxiaoxi on 16/3/12.
// Copyright © 2016年 moxiaoxi. All rights reserved.
//
using namespace std;
#include <iostream>
//先将A杆上n－1移动到B杆上，再将最大盘的移动到C杆，然后，将B杆上n－1移动到C杆（A－>B,B->C移动需要借助第三块板）
void hannoi(int n, char from,char buffer,char dest)
{
if(n==1)
cout<<"从"<<from<<"移动"<<n<<"号圆盘，到"<<dest;
else
{
hannoi(n-1,from,dest,buffer);//通过C，将A上的n－1块移动到B上
cout<<"从"<<from<<"移动"<<n<<"号圆盘，到"<<dest;
hannoi(n-1, buffer, from, dest);
}
return;
}
int main() {
unsigned n;
cin>>n;
hannoi( n,'A','B','C');
return 0;
}
非递归代码
使用栈，压栈的顺序和递归代码顺序有出入！务必注意！
using namespace std;
#include <iostream>
struct han
{
int begin,end;
char from,buffer,dest;
han(){};
han(int begin,int end,char from,char buffer,char dest):begin(begin),end(end),from(from),buffer(buffer),dest(dest){};
};
void hannoi(int n, char from,char buffer, char dest)
{
stack<han> stk;
han temp;
stk.push(han(1,n,from,buffer,dest));
while(!stk.empty()){
temp=stk.top();
stk.pop();
if( temp.begin ==temp.end)
cout<<"从"<<temp.from<<"移动"<<temp.begin<<"号圆盘，到"<<temp.dest<<endl;
else
{
stk.push(han(temp.begin,temp.end-1,temp.buffer,temp.from,temp.dest));
stk.push(han(temp.end,temp.end,temp.from,temp.buffer,temp.dest));
stk.push(han(temp.begin,temp.end-1,temp.from,temp.dest,temp.buffer));
}
}
}
int main() {
unsigned n;
cin>>n;
hannoi( n,'A','B','C');
return 0;
}
集合划分问题
问题描述：
n个元素的集合{1,2,…, n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：
{ {1}，{2}，{3}，{4}}，
{ {1，2}，{3}，{4}}，
{ {1，3}，{2}，{4}}，
{ {1，4}，{2}，{3}}，
{ {2，3}，{1}，{4}}，
{ {2，4}，{1}，{3}}，
{ {3，4}，{1}，{2}}，
{ {1，2}，{3，4}}，
{ {1，3}，{2，4}}，
{ {1，4}，{2，3}}，
{ {1，2，3}，{4}}，
{ {1，2，4}，{3}}，
{ {1，3，4}，{2}}，
{ {2，3，4}，{1}}，
{ {1，2，3，4}}
给定正整数n，计算出n个元素的集合{1,2,.., n }可以划分为多少个不同的非空子集。
##解决思路： 对于n个元素的集合，可以划分成由m(1<=m<=n)个子集构成的子集，如 { {1}，{2}，{3}，{4}}就是由4个子集构成的非空子集。
假设f(n,m)表示将n个元素的集合划分成由m个子集构成的集合的个数，那么可以这样来看：
1)若m==1，则f(n,m)=1;
2)若n==m，则f(n,m)=1;
3)若非以上两种情况，f(n,m)可以由下面两种情况构成
a.向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；
b.向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。
因此：
f（n，m）＝1 (m==1||n==m)
f(n,m)=f(n-1,m-1)+m*f(n-1,m) (m<n&&m!=1) ----
代码：
//
// main.cpp
// set
//
// Created by moxiaoxi on 16/3/13.
// Copyright © 2016年 moxiaoxi. All rights reserved.
//
#include <stdio.h>
unsigned setpart(unsigned n, unsigned m)
{
if(m==1||n==m)
return 1;
else
return setpart(n-1,m-1)+setpart(n-1,m)*m;
}
int main(int argc, const char * argv[]) {
unsigned m,n,out;
FILE *fp,*fpout;
if(argc!=3){
printf("have not enter two file name strike any key exit");
getchar();
return -1;
}
if((fp=fopen(argv[1],"r"))==NULL){
printf("\nCannot open input file strike any key exit!");
getchar();
return -1;
}
if((fpout=fopen(argv[2],"w"))==NULL){
printf("\nCannot open output file strike any key exit!");
getchar();
return -1;
}
fscanf(fp,"%d",&n);
fscanf(fp,"%d" ,&m);
out=setpart(n,m);
fprintf(fpout,"%d",out);
return 0;
}
