歴代試験問題帯点数(dfs全配列フィルタリング)

2017 ワード

問題の説明
100は、100=3+69258/714のバンドスコアの形で表すことができる.
100=82+3546/197と表すこともできます.
注意特徴:帯分数では、1~9の数字がそれぞれ1回しか現れず(0を含まない).
このような帯分数は,100に11種類の表現がある.
入力フォーマット
標準入力から正の整数N(N<1000*1000)を読み込む
出力フォーマット
プログラムは、この数字がデジタル1~9で繰り返しても漏れなくバンド点数で表される全種数を構成するように出力する.
注意:各表示を出力する必要はありません.どれだけの表示方法があるかを統計します.
サンプル入力1
100
サンプル出力1
11
サンプル入力2
105
サンプル出力2
6
300篇の博文の記念、品質はすべて高くありませんが、結局やっと半年学んで、引き続き努力します
考え方:
1-9の全配列にn==n 1+n 2/n 3条件を満たすものをスクリーニングすることに加えて1組の解
フィルタリング方法:n 1を下付き0から6、n 2をn 1下付き+1から7、n 3をn 2下付き+1から
8までn 2%n 3=0
STLコード:
#include
#include
#include
using namespace std;
int a[9]={1,2,3,4,5,6,7,8,9},c=0;
void js(int n)
{
	int i,j,k,n1=0,n2=0,n3=0;
	for (i=0;i<=6;i++)
	{
		n1=n1*10+a[i];
		if (n1>=n)
		 break;
		 n2=0;
		for (j=i+1;j<=7;j++)
		{
			n2=n2*10+a[j];
			n3=0;
			for (k=j+1;k<=8;k++)
			{
				n3=n3*10+a[k];
				if (n3>n2)
				break;	
			}
			if(k>=8)
			if (n2%n3==0&&n==n1+n2/n3)
			 c++;
		}
	}
}
int main()
{
	int i,n;
	cin>>n;
	do
	{
		js(n);
	}while (next_permutation(a,a+9));
	cout<

dfsコード:
#include
#include
using namespace std;
int a[10]={0},v[10]={0},n,c=0;
void js()
{
	int i,j,k,n1=0,n2=0,n3=0;
	for (i=0;i<=6;i++)
	{
		n1=n1*10+a[i];
		if (n1>=n)
		 break;
		 n2=0;
		for (j=i+1;j<=7;j++)
		{
			n2=n2*10+a[j];
			n3=0;
			for (k=j+1;k<=8;k++)
			{
				n3=n3*10+a[k];
				if (n3>n2)
				break;	
			}
			if(k>=8)
			if (n2%n3==0&&n==n1+n2/n3)
			 c++;
		}
	}
}
void dfs(int x)
{
	int i;
	for (i=1;i<=9;i++)
	{
		if (!v[i])
		{
			 	a[x]=i;
			 	v[i]=1;
			if (x<8)
			dfs(x+1);
			else
			{
				js();
			}
			v[i]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(0);
	cout<