汉诺塔问题和集合划分问题

本文总阅读量
Posted by Xiaoxi on March 13, 2016

#汉诺塔问题

简介

汉诺塔是根据一个传说形成的数学问题:

有三根杆子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;
}