抽签
//X星球要派出一个5人组成的观察团前往W星。
//其中：
//A国最多可以派出4人。
//B国最多可以派出2人。
//C国最多可以派出2人。
//....
//那么最终派往W星的观察团会有多少种国别的不同组合呢？
//下面的程序解决了这个问题。
//数组a[] 中既是每个国家可以派出的最多的名额。
//程序执行结果为：
//DEFFF
//CEFFF
//CDFFF
//CDEFF
//CCFFF
//CCEFF
//CCDFF
//CCDEF
//BEFFF
//BDFFF
//BDEFF
//BCFFF
//BCEFF
//BCDFF
//BCDEF
//....
//(以下省略，总共101行)
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
int ans = 0;
void f(int a[], int k, int m, char b[])//对应国家最多可排除的人数，对应国家，人数，输出值
{
int i, j;
if (k == N) {
b[M] = 0;
if (m == 0)
{
ans++;
printf("%d", ans);//检验
printf("%s\n", b);
}
return;
}
for (i = 0; i <= a[k]; i++) {
for (j = 0; j < i; j++) b[M - m + j] = k + 'A';//对应国家派出j人
f(a, k + 1, m - j, b); //填空位置
}
}
int main()
{
int a[N] = { 4,2,2,1,1,3 };//对应国家最多可排除的人数
char b[BUF];//输出
f(a, 0, M, b);
return 0;
}
//仔细阅读代码，填写划线部分缺少的内容。
//注意：不要填写任何已有内容或说明性文字。
凑算式
//凑算式
// B DEF
//A + — + -——— = 10
// C GHI
//（如果显示有问题，可以参见【图1.jpg】）
//这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
//比如：
//6 + 8 / 3 + 952 / 714 就是一种解法，
//5 + 3 / 1 + 972 / 486 是另一种解法。
//这个算式一共有多少种解法？
//注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
#include<iostream>
using namespace std;
int main()
{
int ans = 0;
for (int a = 1; a < 10; a++)
{
for (int b = 1; b < 10; b++)
{
if (b != a)
{
for (int c = 1; c < 10; c++)
{
if (c != a && c != b)
{
for (int d = 1; d < 10; d++)
{
if (d != a && d != b && d != c)
{
for (int e = 1; e < 10; e++)
{
if (e != a && e != b && e != c && e != d)
{
for (int f = 1; f < 10; f++)
{
if (f != a && f != b && f != c && f != d && f != e)
{
for (int g = 1; g < 10; g++)
{
if (g != a && g != b && g != c && g != d && g != e && g != f)
{
for (int h = 1; h < 10; h++)
{
if (h != a && h != b && h != c && h != d && h != e && h != f && h != g)
{
for (int i = 1; i < 10; i++)
{
if (i != a && i != b && i != c && i != d && i != e && i != f && i != g && i != h)
{
int up = d * 100 + e * 10 + f;
int down = g * 100 + h * 10 + i;
if (a + (b * down + c * up) / (c * down) == 10 && (b * down + c * up) % (c * down) == 0)//注：1.int型加减乘除有四舍五入 2.多个除式要化为一个除式在作取余是否等零的判断（避免：可用double型计算）
{
ans++;
printf("%d %d %d %d %d\n", a, b, c, up, down);//检验
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
printf("%d", ans);
return 0;
}方格填数
//如下的10个格子
// [][][]( 0 1 2)
//[][][][](3 4 5 6)
//[][][] (7 8 9 )
//（如果显示有问题，也可以参看【图1.jpg】）
//填入0~9的数字。要求：连续的两个数字不能相邻。
//（左右、上下、对角都算相邻）
//一共有多少种可能的填数方案？
//请填写表示方案数目的整数。
//注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
//暴力
//#include<iostream>
//#include <algorithm>
//using namespace std;
//int ans = 0;
//int main()
//{
// int array[10] = { 0,1,2,3,4,5,6,7,8,9 };
// do
// {
// if (array[0] != array[1] + 1 && array[0] != array[1] - 1 && array[0] != array[5] + 1 && array[0] != array[5] - 1 && array[0] != array[4] + 1 && array[0] != array[4] - 1 && array[0] != array[3] + 1 && array[0] != array[3] - 1)//注1.#include <cmath> abs()取绝对值化简if条件 2.if条件也可用||
// {
// if (array[1] != array[2] + 1 && array[1] != array[2] - 1 && array[1] != array[6] + 1 && array[1] != array[6] - 1 && array[1] != array[5] + 1 && array[1] != array[5] - 1 && array[1] != array[4] + 1 && array[1] != array[4] - 1)
// {
// if (array[2] != array[6] + 1 && array[2] != array[6] - 1 && array[2] != array[5] + 1 && array[2] != array[5] - 1)
// {
// if (array[3] != array[4] + 1 && array[3] != array[4] - 1 && array[3] != array[8] + 1 && array[3] != array[8] - 1 && array[3] != array[7] + 1 && array[3] != array[7] - 1)
// {
// if (array[4] != array[5] + 1 && array[4] != array[5] - 1 && array[4] != array[9] + 1 && array[4] != array[9] - 1 && array[4] != array[8] + 1 && array[4] != array[8] - 1 && array[4] != array[7] + 1 && array[4] != array[7] - 1)
// {
// if (array[5] != array[6] + 1 && array[5] != array[6] - 1 && array[5] != array[9] + 1 && array[5] != array[9] - 1 && array[5] != array[8] + 1 && array[5] != array[8] - 1)
// {
// if (array[6] != array[9] + 1 && array[6] != array[9] - 1)
// {
// if (array[7] != array[8] + 1 && array[7] != array[8] - 1)
// {
// if (array[8] != array[9] + 1 && array[8] != array[9] - 1)
// {
// ans++;
// }
// }
// }
// }
// }
// }
// }
// }
// }
// } while (next_permutation(array, array + 10));
// printf("%d", ans);
// return 0;
//}
//dfs二维数组
#include<iostream>
#include<math.h>
using namespace std;
int a[5][6];
int vis[10];
int ans;
bool check(int i, int j) { //检查9宫格
for (int x = i - 1; x <= i + 1; x++) {
for (int y = j - 1; y <= j + 1; y++) {
if (abs(a[x][y] - a[i][j]) == 1)
return false;
}
}
return true;
}
void dfs(int x, int y) {
if (x == 3 && y == 4) { //出口
ans++;
return;
}
//从0-9抓一个
for (int i = 0; i < 10; i++) {
if (vis[i] == 0) { //i没有被用过
a[x][y] = i; //填数
if (!check(x, y)) {
//数不合法，说明两个数是连续的，则退回到刚才那个点，继续寻找，适合的数
a[x][y] = -10;//复原，用其他数填
continue;
}
vis[i] = 1; //标记已访问
if (y == 4)
dfs(x + 1, 1); //换行
else
dfs(x, y + 1); //继续右边格子
{vis[i] = 0; //回溯
a[x][y] = -10; }
}
}
}
void init() { //将5x6的格子先用-10填满
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
a[i][j] = -10;
}
}
}
int main() {
init();
dfs(1, 2);
cout << ans << endl;
return 0;
}
剪邮票
图1 图2 图3
//如【图1.jpg】, 有12张连在一起的12生肖的邮票。
//现在你要从中剪下5张来，要求必须是连着的。
//（仅仅连接一个角不算相连）
//比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
//请你计算，一共有多少种不同的剪取方法。
//12选5的条件全排列
//请填写表示方案数目的整数。
//注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include<iostream>
#include <algorithm>
using namespace std;
int ans = 0;
int array[12] = { 0,0,0,0,0,0,0,1,1,1,1,1 };//12选5 注：字典序，从所给开始从小到大排序
void dfs(int tailor[3][4], int x, int y)//dfs连通性检测(十字型四向蔓延）
{
tailor[x][y] = 0;//已经判断过的赋0，避免影响后续的连通性检测
if (x - 1 >= 0 && tailor[x - 1][y] == 1)
{
dfs(tailor, x - 1, y);
}
if (x + 1 <= 2 && tailor[x + 1][y] == 1)
{
dfs(tailor, x + 1, y);
}
if (y - 1 >= 0 && tailor[x][y - 1] == 1)
{
dfs(tailor, x, y - 1);
}
if (y + 1 <= 3 && tailor[x][y + 1] == 1)
{
dfs(tailor, x, y + 1);
}
}
bool check(int array[])//连通性检测
{
int tailor[3][4];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
tailor[i][j] = array[i * 4 + j];
}
}
int count = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
if (tailor[i][j] == 1)
{
dfs(tailor, i, j);
count++;
}
}
}
return count == 1;
}
int main()
{
do
{
if (check(array))
{
ans++;
}
} while (next_permutation(array, array + 12));//next_permutation对于存在重复数字的数组能保障不重复
printf("%d", ans);
return 0;
}
交换瓶子
//有N个瓶子，编号 1 ~N，放在架子上。
//比如有5个瓶子：
//2 1 3 5 4
//要求每次拿起2个瓶子，交换它们的位置。
//经过若干次后，使得瓶子的序号为：
//1 2 3 4 5(看作数组 array[i]=i)
//对于这么简单的情况，显然，至少需要交换2次就可以复位。
//如果瓶子更多呢？你可以通过编程来解决。
//输入格式为两行：
//第一行 : 一个正整数N（N < 10000）, 表示瓶子的数目
//第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
//输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
//例如，输入：
//5
//3 1 2 5 4
//程序应该输出：
//3
//再例如，输入：
//5
//5 4 3 2 1
//程序应该输出：
//2
//资源约定：
//峰值内存消耗 < 256M
//CPU消耗 < 1000ms
//请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
//所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
//注意 : main函数需要返回0
//注意 : 只使用ANSI C / ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
//注意 : 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
//提交时，注意选择所期望的编译器类型。
#include<iostream>
using namespace std;
int N;
int ans = 0;
int bottle[10000];
int position(int x)//返回脚标
{
for (int i = 1; i <= N; i++)
{
if (bottle[i] == x)
{
return i;
}
}
}
void swap(int i, int j)
{
int t = bottle[i];
bottle[i] = bottle[j];
bottle[j] = t;
}
int main()
{
scanf("%d", &N);
for (int i = 1; i <= N; i++)
{
scanf("%d", &bottle[i]);
}
for (int i = 1; i <= N; i++)
{
if (bottle[i] == i)
{
continue;
}
else
{
swap(position(i), i);
ans++;
}
}
printf("%d\n", ans);
return 0;
}快速排序
//排序在各种场合经常被用到。
//快速排序是十分常用的高效率的算法。
//其思想是：先选一个“标尺”，
//用它把整个队列过一遍筛子，
//以保证：其左边的元素都不大于它，其右边的元素都不小于它。
//这样，排序问题就被分割为两个子区间。
//再分别对子区间排序就可以了。
//下面的代码是一种实现，请分析并填写划线部分缺少的代码。
#include <stdio.h>
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)//找标尺脚标，将小于标尺的数放到左侧，大于标尺的数放到右侧
{
int i = p;
int j = r + 1;
int x = a[p];//左端点（标尺）
while (1) {
while (i < r && a[++i] < x);
while (a[--j] > x);
if (i >= j) break;
swap(a, i, j);
}
swap(a,p,j);//填空位置
return j;
}
void quicksort(int a[], int p, int r)
{
if (p < r) {//a[0]<a[11]
int q = partition(a, p, r);
quicksort(a, p, q - 1);//标尺两边分别作比较
quicksort(a, q + 1, r);
}
}
int main()
{
int i;
int a[] = { 5,13,6,24,2,8,19,27,6,12,1,17 };
int N = 12;
quicksort(a, 0, N - 1);
for (i = 0; i < N; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
//注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。
煤球数目
//有一堆煤球，堆成三角棱锥形。具体：
//第一层放1个，//0+1
//第二层3个（排列成三角形），//0+1+2
//第三层6个（排列成三角形），//0+1+2+3
//第四层10个（排列成三角形），//0+1+2+3+4
//....
//如果一共有100层，共有多少个煤球？
//请填表示煤球总数目的数字。
//注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include<iostream>
using namespace std;
int ans = 0;
int sum(int level)
{
if (level==101)
{
return ans;
}
for (int i = 0; i <= level; i++)
{
ans += i;
}
sum(level += 1);
}
int main()
{
sum(0);
printf("%d", ans);
return 0;
}生日蜡烛
//某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
//现在算起来，他一共吹熄了236根蜡烛。
//请问，他从多少岁开始过生日party的？
//请填写他开始过生日party的年龄数。
//注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include<iostream>
using namespace std;
int main()
{
for (int start = 0; start <= 236; start++)
{
for (int end = 0; end <= 236; end++)
{
int sum = 0;
for (int i = start; i < end; i++)
{
sum += i;
}
if (sum == 236)
{
printf("%d %d", start, end);
}
}
}
return 0;
}四平方和
//四平方和定理，又称为拉格朗日定理：
//每个正整数都可以表示为至多4个正整数的平方和。
//如果把0包括进去，就正好可以表示为4个数的平方和。
//比如：
//5 = 0 ^ 2 + 0 ^ 2 + 1 ^ 2 + 2 ^ 2
//7 = 1 ^ 2 + 1 ^ 2 + 1 ^ 2 + 2 ^ 2
//（ ^ 符号表示乘方的意思）
//对于一个给定的正整数，可能存在多种平方和的表示法。
//要求你对4个数排序：
//0 <= a <= b <= c <= d
//并对所有的可能表示法按 a, b, c, d 为联合主键升序排列，最后输出第一个表示法
//程序输入为一个正整数N(N < 5000000)
//要求输出4个非负整数，按从小到大排序，中间用空格分开
//例如，输入：
//5
//则程序应该输出：
//0 0 1 2
//再例如，输入：
//12
//则程序应该输出：
//0 2 2 2
//再例如，输入：
//773535
//则程序应该输出：
//1 1 267 838
//资源约定：
//峰值内存消耗 < 256M
//CPU消耗 < 3000ms
//请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
//所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
#include<iostream>
#include<cmath>
using namespace std;
int N;
int main()
{
scanf("%d", &N);
int n = sqrt(N);//#include<cmath> sqrt()取平方
for (int a = 0; a <= n; a++)
{
for (int b = a; b <= n; b++)
{
for (int c = b; c <= n; c++)
{
for (int d = c; d <= n; d++)
{
if (a * a + b * b + c * c + d * d == N)
{
printf("%d %d %d %d", a, b, c, d);
return 0;
}
}
}
}
}
}