[Aha]坑爹的奥数

2019-11-06 06:34:59

字体：大中小

来源：转载

供稿：网友

题目：见啊哈算法p58页，一开始用暴力枚举的方式写的，后p79页介绍如何使用DFS做。很适合熟悉DFS的写法。分析：按照套路来

void dfs(int step){ 判断边界; 尝试每一种可能for(int i = 1 ; i <= n ; i++){ 继续下一步dfs(step+1); } 返回; }

代码：

#include<iostream>#include<cstdio>using namespace std ;int total = 0 ;int a[10],book[10];void dfs(int step){//step表示现在站在第几个盒子 if(step == 10){//如果站在第10个盒子面前，则表示前9个盒子已经放好了扑克牌 //判断是否满足等式 if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9]){ PRintf("%d%d%d+%d%d%d=%d%d%d/n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]); total ++; } return ; } //此时站在第step个盒子面前，一一尝试应该放哪一张牌 for(int i = 1 ; i <= 9 ; i++){ //判断扑克牌i是否还在手上 if(book[i]==0){//book[i]等于0表示扑克牌还在手上 //开始尝试扑克牌i a[step] = i; book[i] = 1; //dfs：递归调用 dfs(step+1); book[i] = 0 ; //回溯时将刚刚尝试的扑克牌i收回 } } return ; }int main(){ dfs(1); printf("total=%d/n",total/2); return 0 ; }

上一篇：linux下安装redis

下一篇：MySQL存储过程传递中文参数