首页 > 代码库 > Sicily-1050 深度优先搜索
Sicily-1050 深度优先搜索
一． 题意
给出5个数和4则运算，看能不能算出目标值出来，如果算不出来就算出比目标值小的最大值。深搜：每一步选两个数做运算，然后算出的结果作为下一步的其中一个操作数。每一步选数有C(5,2)种，每两个数间又有5种运算结果（减法位置不同算两种）。
二． 做法：
用数组存储放进来的5各操作数，并在这个过程中用来存放中间答案，没进行一次计算操作数的个数就会减少一个。注意每一步深搜之后都要恢复原本状态。
三． 源码
1 // 2 // main.cpp 3 // sicily-1050 4 // 5 // Created by ashley on 14-10-10. 6 // Copyright (c) 2014年 ashley. All rights reserved. 7 // 8 9 #include <iostream>10 using namespace std;11 int storing[5];12 int answer, result;13 void depthSearch(int size)14 {15 for (int i = 0; i < size; i++) {16 if (storing[i] > result && storing[i] <= answer) {17 result = storing[i];18 }19 }20 if (result == answer) {21 return;22 }23 if (size == 1) {24 return;25 }26 for (int i = 0; i < size - 1; i++) {27 for (int j = i + 1; j < size; j++) {28 int left, right;29 left = storing[i];30 right = storing[j];31 storing[j] = storing[size - 1];32 //add and decrease a number33 storing[i] = left + right;34 depthSearch(size - 1);35 //subtract and decrease a number36 storing[i] = left - right;37 depthSearch(size - 1);38 //subtract and decrease a number39 storing[i] = right - left;40 depthSearch(size - 1);41 //multiply and decrease a number42 storing[i] = left * right;43 depthSearch(size - 1);44 //divide and decrease a number45 if (left != 0 && right % left == 0) {46 storing[i] = right / left;47 depthSearch(size - 1);48 }49 if (right != 0 && left % right == 0) {50 storing[i] = left / right;51 depthSearch(size - 1);52 }53 storing[i] = left;54 storing[j] = right;55 }56 }57 }58 int main(int argc, const char * argv[])59 {60 int runs;61 cin >> runs;62 while (runs--) {63 for (int i = 0; i < 5; i++) {64 cin >> storing[i];65 }66 cin >> answer;67 result = -101;68 depthSearch(5);69 cout << result << endl;70 }71 return 0;72 }
Sicily-1050 深度优先搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。