蓝桥杯问题第16省Ca6 - 寒假作业(全排列问题) 现在的小学数学题没那么好玩了。来看看这份寒假作业吧:□ + □ = □ □ - □ = □ □□ × □ = □ □ ÷ □ = □ 每个平方的代入法
最编程
2024-04-20 19:00:15
...
题目描述
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业:
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
每个方块代表1~13中的某一个数字,但不能重复。
比如:
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及:
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。(加法,乘法交换律后算不同的方案)
你一共找到了多少种方案?
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
输入
没有输入。
输出
1个整数
思路
参考我之前的回答,这依然是一道典型的组合并排列问题。也就是在13个数里面找12个数,并排列,看是否符合条件。但是因为13-12=1,也就是选出12个数之后只剩下了一个数,这样的话也可以用全排列直接来写,如果剩下了两个数,并且用全排列写的话,就会产生重复的问题,那么结果就要除以剩余数的个数的阶乘。(这个问题可以参考下面这篇博客:
蓝桥杯真题 13省2-马虎的算式)
那么这道题只需要全排列遍历出所有位置的数,并对每次遍历的结果进行检查,如果合适就使num+1;
简单实用的全排列模板献上:
全排列模板
#include <stdio.h>
#define N 13
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
int num =0;
void disp()
{
if((a[0]+a[1]==a[2]) && (a[3]-a[4]==a[5]) && (a[6]*a[7]==a[8]) && (a[10]*a[11]==a[9]))
num++;
}
void change(int *a,int i)
{
int t=a[0];
a[0]=a[i];
a[i]=t;
}
void permit(int *a,int n)
{
int i;
if(n==1)
{
disp();
return;
}
for(i=0;i<n;i++)
{
change(a,i);
permit(a+1,n-1);
change(a,i);
}
}
int main ()
{
permit(a,N);
printf("%d",num);
return 0;
}
答案:64
运行示例
由于数据较多,运行时间可能会比较长哦!
C++全排列函数版:
#include <stdio.h>
#include <algorithm>
using namespace std;
int num = 0;
void process(int a[])
{
if((a[0]+a[1]==a[2]) && (a[3]-a[4]==a[5]) && (a[6]*a[7]==a[8]) && (a[10]*a[11]==a[9]))
num++;
}
int main ()
{
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
int n = 13;
do
{
process(a);
}while(next_permutation(a,a+n));
printf("%d",num);
return 0;
}