翻币问题 题解

翻币问题

问题描述

有N个硬币(6<=N<=20000)全部正面朝上排成一排，每次将其中5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。试编程找出步数最少的翻法，输出最少步数及翻法。

input

从键盘输入一个正整数N(6<=N<=20000)，表示硬币的数量。

output

第1行：一个整数，表示最少步数
第2行至最后一行：先是一个整数，表示步骤序号（从0开始编号），后接一个":"，再接当前硬币的状态（用一个整数表示正面朝上的硬币的个数）

样例

输入
6

输出
6

样例解释
0:6 (第0步结果:6个硬币正面朝上)
1:1 (第1步结果:1个硬币正面朝上)
2:4 (第2步结果:4个硬币正面朝上)
3:3 (第3步结果:3个硬币正面朝上)
4:2 (第4步结果:2个硬币正面朝上)
5:5 (第5步结果:5个硬币正面朝上)
6:0 (第6步结果:0个硬币正面朝上)
6 (最少用6步实现全部反面朝上)

问题分析

由题可得知有6种翻法：

原正个数	原负个数	翻后正个数	翻后负个数
5	0	-5	+5
4	1	-3	+3
3	2	-1	+1
2	3	+1	-1
1	4	+3	-3
0	5	+5	-5

判断当前状态是否满足翻的条件，并且翻后状态没有出现过
是就 tail++，放入队尾，将翻后状态=1
如果当前状态正数个数=0，输出步数
别的就套模板啦，我只是个蒟蒻

代码

 #include<iostream>
#include<cstdio>
using namespace std;
int a[20100],h,t,n;
int fz[7]={0,5,4,3,2,1,0},ff[7]={0,0,1,2,3,4,5}; 
struct c{
	int s,b,f;
}s[20100];
int main()
{
	scanf("%d",&n);
	s [1] .s=n; s[1].b=0; s[1].f=0; // 付初值，s 是正数个数，b 是步数，f 是父节点
	h=0; t=1;
	a[n]=1; // 状态出现，设为1
	do{
		h++;
		for (int i=1;i<=6;i++)
		    if (s[h].s>=fz[i]&&n-s[h].s>=ff[i]&&a[s[h].s-fz[i]+ff[i]] = =  0)
		    // 判断当前状态是否满足翻的条件，并且翻后状态没有出现过
		    {
		    	t++;
		    	s[t].s=s[h].s-fz[i]+ff[i];
		    	s[t].b=s[h].b+1;
		    	s[t].f=h; //放入队尾
		    	a[s[t].s]=1; // 保存当前状态出现
		    	if (s[t].s = = 0)
		    	{
		    		//int k=s[t].f;
		    		//while (k!=0)
		    		//{
		    		//	cout<<s[k].s<<" "<<s[k].b<<endl;
		    		//	k=s[k].f;
		    		//}  用来检测程序，可看每步的正数个数
		    		cout<<s[t].b<<endl; //输出最后步数
		    		return 0;
		    	}
		    }
	}while (h<t);
	return 0;
}