歷屆試題 帶分數 時間限制：1.0s 記憶體限制：256.0MB 時間限制：1.0s 記憶體限制：256.0MB 問題描述 100 可以表示為帶分數的形式：100 = 3 + 69258 / 714。 還可以表示為：100 = 82 + 3546 / 197。 註意特征：帶分數中，數字1~9分別出現且只 ...
歷屆試題 帶分數 時間限制：1.0s 記憶體限制：256.0MB 問題描述
100 可以表示為帶分數的形式：100 = 3 + 69258 / 714。
還可以表示為：100 = 82 + 3546 / 197。
註意特征：帶分數中，數字1~9分別出現且只出現一次（不包含0）。
類似這樣的帶分數，100 有 11 種表示法。
輸入格式從標準輸入讀入一個正整數N (N<1000*1000)
輸出格式程式輸出該數字用數位1~9不重覆不遺漏地組成帶分數表示的全部種數。
註意：不要求輸出每個表示，只統計有多少表示法！
樣例輸入1 100 樣例輸出1 11 樣例輸入2 105 樣例輸出2 6 解題思路：首先需要瞭解一下全排列，以及全排列的演算法，我是直接搜的演算法，在寫這個博客之前表示沒還沒仔細研究過，但是感覺很好理解，然後就是將每一個數都嘗試一邊看是不是帶分數，也就是迴圈確定a和b的位置，剩下就是c，判斷一下就好了#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
int sum;
int n;
int x,y,z;
//交換
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
//全排列遞歸演算法
void Perm(int list[], int k,int m)
{
//list 數組存放排列的數，K表示層 代表第幾個數，m表示數組的長度
if(k==m)
{
//K==m 表示到達最後一個數，不能再交換，最終的排列的數需要輸出；
x=0;y=0;z=0;
for(int i=0;i<7;i++){
x= x*10+list[i];
y=0;
for(int j=i+1;j<8;j++){
y=y*10+list[j];
z=0;
for(int k1=j+1;k1<=8;k1++){
z=z*10+list[k1];
if(k1==8&&y>z&&y%z==0&&x+y/z==n){
sum++;
// cout<<x<<" "<<y<<" "<<z<<" "<<y/z<<" "<<y%z<<endl;
}
}
}
}
}
else
{
for(int i=k; i<=m; i++)
{
swap(list[i],list[k]);
Perm(list,k+1,m);
swap(list[i], list[k]);
}
}
}
int main()
{
int a[]= {1,2,3,4,5,6,7,8,9 };
sum=0;
cin>>n;
Perm(a,0,8);
cout<<sum;
return 0;
}
