解题思路:将排队看做M人的排列问题,在M!个排列中寻找符合条件的排列(排队时只要一元的人数大于等于2元就有零钱),采用回溯法(深度优先算法)
恭喜我成为继小方之后第二个AC此题的男人
#include <stdio.h> #define N 10 void search(int ); void swap(int ,int ); int a[N]={0}; //待排序数据 int b[N]={0}; //队伍,不大于10 int x=2,y=2,z=4; int count=0; //总次数 int one=0; //已经站队的1元人数 int two=0; //2元人数 int main() { scanf("%d%d%d",&z,&x,&y); int i; for(i=0;i<x;i++) a[i]=1; //一元的小孩为1,两元的为0 for(;i<z;i++) a[i]=0; search(0); printf("%d\n",count); return 0; } void search(int n){ if(n==z){ //队伍站满 count++; //计数 return ; } else{ int j=0; for(j=0;j<z;j++){ if(b[j]==0){ //判断第j人是否已入队 b[j]=1; //第j个人站入 if(a[j]) one++; //站入队伍的为1元 else two++; //站入为2元 if(one>=0 && two>=0 && one>=two)//如果已入队1元大于2元,则有零钱 search(n+1); //判断下一个位置 if(a[j]) one--; else two--; //回溯 b[j]=0; } } } } void swap(int x,int y){ int t=a[x]; a[x]=a[y]; a[y]=t; }
0.0分
0 人评分
愚蠢的摄影师 (C++代码)浏览:899 |
1024题解浏览:799 |
班级人数 (C语言代码)浏览:911 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:454 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:652 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:376 |
C语言训练-百钱百鸡问题 (C语言代码)浏览:495 |
IP判断 (C++代码)浏览:745 |
龟兔赛跑预测 (C++代码)浏览:1164 |
IP判断 (C语言代码)浏览:495 |