带分数题解

问题描述

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<iostream>using namespace std;long n;long coute;void swap(char * a,char * b){ 　　char ch; 　　ch = *a; 　　*a = *b; 　　*b = ch; 　　return ;}void perm(char List[],int first,int last){ 　　if(first>last){ 　　　　int i,j,z,temp,m; 　　　　long a,b,c; 　　　　for(i = 0 ;i<=6;i++){ 　　　　　　a=b=c=0; 　　　　　　for(j = 0;j<=i;j++){ 　　　　　　　　a*=10; 　　　　　　　　a+=List[j]-'0'; 　　　　　　　　} 　　　　　　if(a>n) return;　　//当出现a大于n时，则a的位数已经达到最高位，返回去检验下一个生成的字符串 　　　　　　temp = ((n-a)*(List[8]-'0'));  //通过b=(n-a)*c  来确定b的最后一位数是多少，可以减少循环次数 　　　　　　for(j=i+1;j<8;j++){ 　　　　　　　　if((List[j]-'0')==temp){  //若余下的字符串没有temp 则肯定没有满足条件的B  ，return 　　　　　　　　　　if((j-i)<(8-j)) break; //当b的位数小于c 时 不满足条件，break;生成下一个a 继续检验。

　　　　　　　　　　for(z=i+1;z<=j;z++){ 　　　　　　　　　　　　b*=10; 　　　　　　　　　　　　b+=List[z]-'0'; 　　　　　　　　　　}

　　　　　　　　　　for(;z<=8;z++){ 　　　　　　　　　　　　c*=10; 　　　　　　　　　　　　c+=List[z]-'0'; 　　　　　　　　　　} 　　　　　　　　　　if(b%c==0&&n==(a+b/c)) coute++; 　　　　　　　　} 　　　　　　} 　　　　} 　　}else{ 　　　　for(int i = first;i<=last;i++){ 　　　　　　swap(&List[first],&List[i]); 　　　　　　perm(List,first+1,last); 　　　　　　swap(&List[first],&List[i]); 　　　　} 　　}}

int main(){ 　　char List[]="123456789"; //定义生成全排列字符串的数组 　　cin>>n; 　　coute=0; 　　perm(List,0,8); 　　cout<<coute; 　　return 0;}

转载于:https://www.cnblogs.com/yuanshixingdan/p/5256557.html

相关资源：JAVA上百实例源码以及开源项目