求最小整数——全排列实现

题目描述

如图，将1～10这10个自然数以任意顺序排成一行，填入第一行的10个圆圈中，第二行最中间的圆圈填0，出了这1个圆圈之外，其余每一个圆圈所填的数字都等于它上方与之相连的圆圈中两个数的和，那么第十行的数N最小值是多少？

输入

无

输出

一个正整数

解题思路

将这个图看成是一个10行10列的二维数组，除了第一行和特点的圈，下面每一行的数字都是上方与之相连的圆圈中两个数的和，所以推出a[i][j]=a[i-1][j]+a[i-1][j+1];

代码

#include<bits/stdc++.h>
using namespace std;
int a[10][10];//定义全局变量的二维数组 
int b[10]={1,2,3,4,5,6,7,8,9,10};//存储1到10的元素 
int t;
int main() 
{
	int MIN=INT_MAX;//定义最小值 
	while(next_permutation(b,b+10))//使用c++的全排列内置函数，next是按照字典序升序排列，prev是降序 
	{
		for(int i=0;i<10;i++)
		{
			a[0][i]=b[i];//先存储第一行的值 
		}
		int i,j;
	for(i=1;i<10;i++)
	for(j=0;j<10-i;j++)
	{
		if(i==1&&j==4)//碰到指定的数跳过 
		continue;
		a[i][j]=a[i-1][j]+a[i-1][j+1];
	}
	t=a[9][0];
	MIN=min(t,MIN); //比较每次排列后第十行数的大小 
	}
	cout<<MIN;
}

运行结果

完结。