問題描述
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
#include <stdio.h>
int w=0,n,count=0;
int list[]={1,2,3,4,5,6,7,8,9};
int main()
{
void perm(int a[],int n,int k=-1);
inline void Swap(int &a,int &b);
int GetNum(int list[],int i,int j);
scanf("%d",&n);
int temp=n;
while(temp!=0)
{
temp=temp/10;
w++;
}
perm(list,9);
printf("%d\n",count);
return 0;
}
int GetNum(int list[],int i,int j)
{
//將list[i]到list[j]之間轉換為數字
int k,num=0;
for(k=i;k<=j;k++)
{
num=num*10+list[k];
}
return num;
}
void perm(int a[],int size,int k=-1)
{
int i;
if(k==-1) k=size-1;
if(k==0)
{
//排列結束。
int j,u;//j表示a的末尾位數 不能超過num的位數;u表示bLast所在的位置
int a=0,b=0,c=0,bLast=0;
for(j=0;j<w;j++)
{
a=GetNum(list,0,j);
/*num=a+b/c
變形可以得到
b=(num-a)*c
而cLast=list[8]
可以得到的是
bLast=((num-a)*list[8])%10;
*/
bLast=((n-a)*list[8])%10;
for(u=j+1;u<8;u++)
{
if(list[u]==bLast)
{
b=GetNum(list,j+1,u);
c=GetNum(list,u+1,8);
if(a+b/c==n&&b%c==0) count++;
}
}
}
}
else
{
for(i=0;i<=k;i++)
{
int tmp;
tmp=a[i];
a[i]=a[k];
a[k]=tmp;
perm(a,size,k-1);
tmp=a[i];
a[i]=a[k];
a[k]=tmp;
}
}
}
