翻币问题 题解

翻币问题 题解

翻币问题

问题描述

有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种翻法：

判断当前状态是否满足翻的条件，并且翻后状态没有出现过
是就 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; // 状态出现，设为1do{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;
}