[ACM]简单回溯搜索——猜牌游戏

猜牌游戏

【问题描述】
猜牌游戏：桌上有分别写着1-100的100张牌，游戏者从100张牌子中抽出K张，把K(1<K<100)张牌对应的数字相乘得到一个结果S，然后把结果S告诉挑战者，让挑战者猜游戏者K张牌的可能组合。游戏者也可能报一个假的结果S给挑战者，也就是不存在K张牌相乘得到该结果，这时挑战者要辨别游戏者是否说谎。挑战者猜中则为赢，猜错就为输。

【输入形式】
从标准输入自然数S和自然数K。

【输出形式】
输出K张牌的所有方式（用空格隔开），每一种方式为一行，在每一行末均输出一个回车符。如果不存在K张牌相乘得到S的情况，则输出LIE。

【输入样例】
100 3
100 5
23205 3

【输出样例】
1 2 50
1 4 25
1 5 20
2 5 10
LIE
3 85 91
5 51 91
7 39 85
7 51 65
13 21 85
13 35 51
15 17 91
17 21 65
17 35 39

该题与Crashing Balloon相似，但较为简单，思路及代码如下：

#include<stdio.h>
//n 已找到的因子数, q 当前因子, a 已找到的因子, num 情况数
void Solve(int s, int k, int n, int q, int a[], int &num){
	if(q > 100){	//若因子超出100，则结束
		return;
	}
	if(n > k){	//若因子数量足够
		if(s == 1){	//若s完全除尽
			for(int i = 1; i <= k; ++i){	//输出所有因子
				printf("%d ", a[i]);
			}
			printf("\n");
			++num;
		}
		return;
	}
	if(s % q == 0){	//若q是s的因子
		a[n] = q;	//存入数组
		Solve(s / q, k, n + 1, q + 1, a, num);	//下层递归
	}
	Solve(s, k, n, q + 1, a, num);	//寻找下一个因子
}

int main(){
	int s, k;
	while(~scanf("%d%d", &s, &k)){
		int num = 0, a[100] = {0};
		Solve(s, k, 1, 1, a, num);
		if(!num)	//若情况总数为0
			printf("LIE\n");	//说明没找到
	}
	return 0;
}

=======================签 名 档=======================
原文地址（我的博客）：http://lanfei.sinaapp.com/2012/06/1325.html
欢迎访问交流，至于我为什么要多弄一个博客，因为我热爱前端，热爱网页，我更希望有一个更加自由、真正属于我自己的小站，或许并不是那么有名气，但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================