算法竞赛入门经典_暴力求解法

　　又有一段时间没写博客了,本应把写博客当成家常便饭的.(对于算法,个人认为没必要刷题,应该更关注算法思路,解题技巧和创新思路)

　　现在进入第七章的学习,暴力求解法

注意: 即使采用暴力法求解问题,对问题进行一定的分析往往会让算法更简洁,高效.

如题:

输入正整数n,按从小到大顺序输出所有形如 abcde / fghij = n 的表达式,其中a - j恰好为数字0-9的一个排列(可以有前导0)2<=n <=79

分析: 枚举0 -9 所有 排列? 没必要,我们只需要枚举fghij 就可以算出abcde,然后判断所有数字都不相同即可.

上代码:

// UVa725 Division
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main() {
  int n, kase = 0; 
  char buf[99];
  while(scanf("%d", &n) == 1 && n) {
    int cnt = 0;
    if(kase++) printf("
");
    for(int fghij = 1234; ; fghij++) {
      int abcde = fghij * n;//题目规则 
      sprintf(buf, "%05d%05d", abcde, fghij);//格式化 
      if(strlen(buf) > 10) break;//长度超过10不符合 
      sort(buf, buf+10);//按顺序排列10个数字 
      bool ok = true;
      for(int i = 0; i < 10; i++)//判断是否都不相同
        if(buf[i] != '0' + i) ok = false;
      if(ok) {
        cnt++;
        printf("%05d / %05d = %d
", abcde, fghij, n);
      }
    }
    if(!cnt) printf("There are no solutions for %d.
", n);
  }
  return 0;
}

　　分数拆分问题:

输入正整数k,扎到所有正整数 x >= y ,使得 1/k = 1/x + 1/y

分析: 既然要枚举,那么我们就要知道枚举的范文,上式进行变形后得: y = (1 + y/x) k  ,易知, y <= 2k ,这样我们就找到了我们的枚举范围了 , k+1 <= y <= 2k

上代码:

//分数拆分 Fractions Again  UVa10976
#include<cstdio>
#include<vector>
using namespace std;

int main(){
    int k;
    while(scanf("%d", &k) == 1 && k){
        vector<int> X, Y;
        for(int y = k+1; y <= k*2; y++){
            if(k*y % (y-k) == 0){
                X.push_back(k*y/(y-k));
                Y.push_back(y);
            } 
        } 
        printf("%d
", X.size());
        for(int i = 0; i < X.size(); i++)
            printf("1/%d = 1/%d + 1/%d
", k, X[i], Y[i]);
    }
    return 0; 
}