算法描述

问题描述

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

---

思考过程

拿到题想到的思路就是用一个长度为9的数组存储这九个数，满足每一位上数字不重复。然后往这九个数中间插运算符，计算结果为输入的数时总数加一就可以。 然后下手写的时候发现我不会遍历这九种数的情况，愁，毕竟我是啥算法都不会的菜鸡×。但是菜鸡会请教大佬，大佬说用dfs遍历很简单。然后给了我一段程序，我就就着程序改的。 dfs深度优先遍历算法简单来说就是，确定一个初始点，然后找其相邻的第二个点，如果点存在并且没有遍历过，就将点作为起始点再进行如上规律遍历，否则找到下一条路径。 伪代码如下： （1）访问顶点v；visited[v]=1；//算法执行前visited[n]=0

（2）w=顶点v的第一个邻接点；

（3）while（w存在）

if（w未被访问） 从顶点w出发递归执行该算法； w=顶点v的下一个邻接点；

这样就第一组产生的数据就是123456789，之后判断走到头了，就return一个，发现仍然没有满足条件的，就再回溯一个，这样数组变成了123456700，倒数第二位又出现一种情况就是9，最后一位8，即123456798 。其实这样说很抽象，画个图表示一下这个过程会方便理解一些。当然这是萌新的方法，一眼就能看出来的大佬就不要用啦~ 通过这种方法遍历出数组后。针对每次生成出数组的情况，对其进行处理。三个数的长度均为1-7的范围内，设置一个函数，将char数组里存放的数字转换为int型数字返回，参数为起始点的下标和数字长度。返回数字后计算num1 + num2 / num3 == N。因为输入的N为正数，所以num2 / num3一定是可整除的，并且num2 >= num3 。所以在判断条件时可以利用这一点减少循环次数。 然后就没了。。

代码表示

/* 0v0 AUTHER: 0_Re5et */ #include <stdio.h> #include <stdlib.h> int p[9] = {0}; //int p[9] = {3, 6, 9, 2, 5, 8, 7, 1, 4}; int N, K=1; int NUM = 0; // 判断数字是否重复出现 int inc(int t) { int i; for(i=0; i<9; i++) { if(p[i] == t) { return 1; } } return 0; } // 输出数组 void Put() { int i, j; int num1, num2, num3; // for(i=0; i<9; i++) // { // printf("%d ", p[i]); // } // printf("\n"); // system("pause"); for(i=1; i<=7; i++) { for(j=1; j<=7-i+1; j++) { if(j < 9-i-j) { continue; } else { num1 = ToNum(0, i); num2 = ToNum(i, j); num3 = ToNum(i+j, 9-i-j); // printf("%d %d %d\n", num1, num2, num3); // system("pause"); if(((num2 % num3) == 0) && (num1 + num2 / num3) == N) { //printf("hahahahaha!!!\n\n"); NUM++; } else { continue; } } } } } // dfs算法 void dfs(int u) { int i, j; if(u == 9) { Put(); return; } for(i=1; i<=9; i++) { if(!inc(i)) { p[u] = i; dfs(u+1); p[u] = 0; } } } // 抽取数组一部分变成数字 int ToNum(int s, int n) { int i, temp = 0; for(i=0; i<n; i++) { temp = temp * 10 + p[s + i]; } return temp; } int main() { scanf("%d", &N); dfs(0); // Put(); printf("%d", NUM); return 0; }

---

注意事项

注意插运算符的时候两个for循环的初始值和结束条件，最开始写的时候就写错了，导致了数组超限然后程序崩溃。 再一个就是注意递归的时候return的使用，用不好就不知道程序执行到哪里去了。很迷 如果想跳出递归又没办法通过return跳出，可以设置标志位在递归函数的开头，直接判断当flag值为1的时候，直接return，这样就return到最外面去了。 然后注意本题中dfs执行完了之后数组置零的过程，起到visit数组标记的作用。 然后把该弄成全局变量的弄一下吧，传参数麻烦的不行。。← 以上。