問題描述

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 記: 題目的類型是：n = a + b/c，求滿足的個數 一開始以為就是簡單的兩個不同比例的"數字+分數"模式,結果在測試其他數據時錯誤, 故將注意力放在a,b,c的比例分配(隱藏條件b >= c) 然而并沒有發現規律... 上網查閱，有一篇博客講到了全排序(http://blog.csdn.net/jopus/article/details/18998403) 還沒開始精細閱讀源碼，被其中的分區的概念刺激 于是有了思路：

a的默認比例為1，依次遞增(a <= n的長度)

將區間總長度(LEN=9)減去a，并取得中值，從而得到b，c的值(b >= c)

每次dfs后，b ++,c --，再次dfs(當b-c > n的長度時，明顯不符條件)

?

源碼如下:

1 #include <stdio.h> 2 #define LEN 9 3 4 int n; 5 int a,b,c; 6 int sum = 0 , len = 0; 7 int ans[LEN+1] = {0}; 8 int num[LEN+1] = {0,1,2,3,4,5,6,7,8,9,}; 9 int f[LEN+1] = {0}; 10 11 void dfs(int x) 12 { 13 int i , j; 14 int x1,x2,x3; 15 if (x > 9) 16 { 17 x = x1 = x2 = x3 = 0; 18 /*1.確定第一個值x1*/ 19 for (i = 0 , j = 1 ; i < a ; i ++) 20 { 21 x1 += ans[++x]*j; 22 j *= 10; 23 } 24 25 /*2.確定分數的分子x2*/ 26 for (i = 0 , j = 1 ; i < b ; i ++) 27 { 28 x2 += ans[++x]*j; 29 j *= 10; 30 } 31 32 /*3.確定分數的分母x3*/ 33 for (i = 0 , j = 1 ; i < c ; i ++) 34 { 35 x3 += ans[++x]*j; 36 j *= 10; 37 } 38 39 if (x2%x3 == 0 && (x1 + x2/x3) == n) 40 { 41 sum ++; 42 //printf("%d+%d/%d\n",x1,x2,x3); 43 } 44 return ; 45 } 46 47 for (i = 1 ; i <= 9 ; i ++) 48 { 49 if (!f[i]) 50 { 51 ans[x] = num[i]; 52 f[i] = 1; 53 dfs(x+1); 54 f[i] = 0; 55 } 56 } 57 58 return ; 59 } 60 61 int main(void) 62 { 63 int i; 64 scanf("%d",&n); 65 i = n; 66 while(i) 67 { 68 i = i/10; 69 len ++; /*獲取n的長度*/ 70 } 71 72 for (a = 1 ; a <= len ; a ++) 73 { 74 i = LEN-a; 75 b = i - i/2; 76 c = i - b; 77 if (b < c)/*b必定為較大區間*/ 78 { 79 b = b^c; 80 c = b^c; 81 b = b^c; 82 } 83 84 /*更改b和c的比例*/ 85 while (c) 86 { 87 dfs(1); 88 b ++; 89 c --; 90 } 91 } 92 printf("%d",sum); 93 return 0; 94 }

?

?

轉載于:https://www.cnblogs.com/mind000761/p/8552007.html

總結

以上是生活随笔為你收集整理的PREV-3_蓝桥杯_带分数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。