一、标题: 1的个数
从1到20的所有数字中含有多少个“1”
仔细数一下，应该是12个。 那么从1到1000的整数中，含有多少个“1”呢？ 请填写该数字。#include题目标题: 1的个数 参考答案：301 得分：10using namespace std;#define MAX 1000int main(){ int count = 0; int m; for(int i = 1; i <= MAX; i++) { int j = i; while(j) { m = j % 10; if(m == 1) { count++; } j = j / 10; } } cout << count << endl;}
二、标题：硬币方案
有50枚硬币，可能包括4种类型：1元，5角，1角，5分。 已知总价值为20元。求各种硬币的数量。 比如：2,34,6,8 就是一种答案。 而 2,33,15,0 是另一个可能的答案，显然答案不唯一。 你的任务是确定类似这样的不同的方案一共有多少个（包括已经给出的2个）？ 直接提交该数字，不要提交多余的内容。#include题目标题：硬币方案 参考答案：50 得分：19using namespace std;#define MAX 20int main(){ int count = 0; for(int i = 0; i <= 20; i++) { for(int j = 0; j <= 40; j++) { for(int k = 0; k <= 200; k++) { for(int m = 0; m <= 400; m++) { if(i + j + m + k == 50 && i * 100 + j * 50 + k *10 + m * 5 == 2000) { count++; } } } } } cout << count << endl;}
三、标题：四方定理
数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。 我们可以通过计算机验证其在有限范围的正确性。 对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。int f(int n, int a[], int idx){ if(n==0) return 1; if(idx==4) return 0; for(int i=(int)sqrt(n); i>=1; i--) { a[idx] = i; if(_______________________) return 1; // 填空 } return 0;}int main(int argc, char* argv[]){ for(;;) { int number; printf("输入整数(1~10亿)："); scanf("%d",&number); int a[] = {0,0,0,0}; int r = f(number, a, 0); printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]); } return 0;}请分析代码逻辑，并推测划线处的代码。 仅把缺少的代码作为答案，通过网页提交。 千万不要填写多余的代码、符号或说明文字！！ #include#include int f(int n, int a[], int idx){ if(n==0) return 1; if(idx==4) return 0; for(int i=(int)sqrt(n); i>=1; i--) { a[idx] = i; if(f(n-i*i, a, idx+1)) return 1; // 填空 } return 0;}int main(int argc, char* argv[]){ //for(;;) //{ int number = 1234567; //printf("输入整数(1~10亿)："); //scanf("%d",&number); int a[] = {0,0,0,0}; int r = f(number, a, 0); printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]); //} return 0;}
四、标题：画表格
在中文Windows环境下，控制台窗口中也可以用特殊符号拼出漂亮的表格来。 比如： ┌─┬─┐│ │ │├─┼─┤ │ │ │└─┴─┘ 其实，它是由如下的符号拼接的：左上 = ┌上 = ┬右上 = ┐左 = ├中心 = ┼右 = ┤左下= └下 = ┴右下 = ┘垂直 = │水平 = ─ 本题目要求编写一个程序，根据用户输入的行、列数画出相应的表格来。 例如用户输入： 3 2 则程序输出： ┌─┬─┐ │ │ │ ├─┼─┤ │ │ │ ├─┼─┤ │ │ │ └─┴─┘ 用户输入： 2 3 则程序输出： ┌─┬─┬─┐ │ │ │ │ ├─┼─┼─┤ │ │ │ │ └─┴─┴─┘ 对于编程题目，要求选手给出的解答完全符合ANSI C++标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。 代码中允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意选择自己使用的编译环境。//画表格#include#include using namespace std;int main(){ int n, m; while (cin >> n >> m) { for(int i = 1; i <= n * 2 + 1; i++) { if(i == 1) { cout << "┌"; for(int j = 1; j <= m - 1; j++) { cout << "─┬"; } cout << "─┐" << endl; } else if(i == n * 2 + 1) { cout << "└"; for(int j = 1; j <= m - 1; j++) { cout << "─┴"; } cout << "─┘" << endl; } else if (i % 2 == 0) { for(int j = 1; j <= m; j++) { cout << "│" << " "; } cout << "│" << endl; } else { cout << "├"; for(int j = 1; j <= m - 1; j++) { cout << "─┼"; } cout << "─┤" << endl; } } } return 0;}
五、标题：分红酒
有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升 开始的状态是 [9,0,0,0]，也就是说：第一个瓶子满着，其它的都空着。 允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。这样的一次倒酒动作称为1次操作。 假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？ 本题就是要求你编程实现最小操作次数的计算。 输入：最终状态（逗号分隔） 输出：最小操作次数（如无法实现，则输出-1） 例如： 输入： 9,0,0,0 应该输出： 0 输入： 6,0,0,3 应该输出： -1 输入： 7,2,0,0 应该输出： 2 对于编程题目，要求选手给出的解答完全符合ANSI C++标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。 代码中允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意选择自己使用的编译环境。BFS，代码写的很挫。
#include2、标题：计算差三角 仔细观察下面的数字组成的三角形： 3 1 4 5 6 2 看出什么特征吗？ 首先，它包含了1~6的连续整数。 重要的是：每个数字都是其下方相邻的两个数字的差（当然是大数减去小数） 满足这样特征的三角形，称为：差三角。 你的任务是找出1~15的整数组成的一个更大的差三角。其形如： ? 4 ? ? ? ? * ? ? ? ? ? ? ? ? 其中，只给出了一个确定的数字：4 请确定出“*” 代表的是哪个一个数字。 直接提交该数字，不要提交多余的内容。#include #include using namespace std;typedef struct Node{ int temp[4]; int setp;}Node;int End[4];const int cap[4] = {9, 7, 4, 2};bool vis[10][10][10][10];queue Q;int bfs(){ while (!Q.empty()) { Q.pop(); } Node pre, next, mid; pre.temp[0] = 9; pre.temp[1] = 0; pre.temp[2] = 0; pre.temp[3] = 0; pre.setp = 0; Q.push(pre); while (!Q.empty()) { pre = Q.front(); Q.pop(); int i, j; for(i = 0; i < 4; i++) { if(pre.temp[i] != End[i]) { break; } } if(i == 4) { return pre.setp; } for(i = 0; i < 4; i++) { for(j = 0; j < 4; j++) { mid = pre; if(i == j) { continue; } if(mid.temp[i] + mid.temp[j] <= cap[j]) { next.temp[i] = 0; next.temp[j] = mid.temp[i] + mid.temp[j]; for(int k = 0; k < 4; k++) { if(k == i || k == j) { continue; } else { next.temp[k] = mid.temp[k]; } } if(!vis[next.temp[0]][next.temp[1]][next.temp[2]][next.temp[3]]) { vis[next.temp[0]][next.temp[1]][next.temp[2]][next.temp[3]] = true; next.setp = mid.setp + 1; Q.push(next); } } else { next.temp[j] = cap[j]; next.temp[i] = mid.temp[i] + mid.temp[j] - cap[j]; for(int k = 0; k < 4; k++) { if(k == i || k == j) { continue; } else { next.temp[k] = mid.temp[k]; } } if(!vis[next.temp[0]][next.temp[1]][next.temp[2]][next.temp[3]]) { vis[next.temp[0]][next.temp[1]][next.temp[2]][next.temp[3]] = true; next.setp = mid.setp + 1; Q.push(next); } } } } } return -1;}int main(){ memset(vis, false, sizeof(vis)); for (int i = 0; i < 4; i++) { cin >> End[i]; } vis[9][0][0][0] = true; cout << bfs() << endl;}
//计算差三角#include5 4 9 7 11 2 8 1 12 10 6 14 15 3 13 请按任意键继续. . . 标题：运送马匹 有1个人，要把n匹马从A村运往B村。 初始时，人和马都在A村。每次骑1匹马牵1匹马，回来时骑1匹马。 已知每匹马从A村到B村需要的时间（数字越大越慢） 两匹马同行时只能迁就较慢者。 求所有马匹都运到B村的最小的运输时间（此时，人和马都在B村）。 程序首先输入一个整数n(n<100)，表示有n匹马。 接着是n行整数，表示马从A村到B村的所用的分钟数（小于1000） 程序输出：1个整数，表示所有马匹均运到B村的最小总耗时。 例如， 输入： 3 1 2 4 程序应输出： 7 输入： 4 1 4 2 5 程序应该输出： 12 对于编程题目，要求选手给出的解答完全符合ANSI C++标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。 代码中允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意选择自己使用的编译环境。 贪心+递归#include using namespace std;int num[10][10];bool vis[20]; //对最后一行选取5个元素进行全排列的选取bool visited[20]; //构造差三角void dfs(int x, int cnt){ int i, j; if(cnt == 6) { memset(visited, false, sizeof(visited)); for(i = 1; i <= 5; i++) { visited[num[5][i]] = true; } for(i = 4; i >= 1; i--) { for(j = 1; j <= i; j++) { int x = abs(num[i+1][j] - num[i+1][j+1]); if(visited[x]) { return; } if(x >= 1 && x <= 15) { visited[x] = true; num[i][j] = x; } } if(i == 2 && j == 1 && num[2][1] != 4) { return; } } if(num[2][1] == 4) { for(i = 1; i <= 5; i++) { for(j = 1; j<= i; j++) { cout << num[i][j] << " "; } cout << endl; } } return; } for(int i = 1; i <= 15; i++) { if(!vis[i]) { vis[i] = true; num[5][cnt] = i; dfs(i, cnt + 1); vis[i] = false; } }}int main(){ memset(vis, false, sizeof(vis)); dfs(1, 1); return 0;}
#include#include #include