佛经名言-会计毕业实习报告

趣味算法题一

在网上回答一个有关算法的问题，觉得有点启发意义，就把它 写在这里，与大家共享，
是心血来潮之解，大都不会是最好的解法，权作抛砖引玉吧。
题目原文的意思如下：
100可以表示为带分数的形式，比如：

其中有一些特殊的情况，例如：

注意上面举的两个例子的特征：带分数中数字1~ 9分别只出现一次（不包括0），类似
的带分数，100有11种表示方法。
题目要求： < br>从键盘输入一个正整数N（N<1000*1000），程序输出该数用数码1~9不重复不遗漏地
组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法，例如，程序运行时 输入100，程序
在屏幕上输出11。
整个算法采用枚举算法的方法。
枚举算法： 就是一一罗列问题的可能的所有解，并且一边罗列一边去检验这个解是否问
题的正真解，是的就采纳它， 不是的就抛弃它。

一．数学分析
对于一个正整数N，可以表示为带分数的形式如下；

从数学知识的要求来说，其中规定：I的范围：[1，N-1]，J >=1，例如：
对于N = 3，有：

所以，根据数学知识可以知道，这样的形式有无穷多个结果，„„。
从题目要求分析，由于有：带分数中数字1~~~~9分别只出现一次（不包括0），这样结
果就变成 了有限个了，题目要求满足：
I、J、M三个数字正好使用到了1、2、3、4、5、6、7、8、9 这9个数字，且仅使用一
次。
用程序实现枚举算法，往往是用循环来实现一一列举，用选择来实现逐步检验。
比如：对于100，它的I值可以是1，2，3，„„99，它的M与J值：
当I = 1， 有：991，1982，2973，„„，随着分子、分母的递增，它们的位数也在逐

步 增多。
从以上分析，I采用记数循环，起始值为1，终止值为N-1；而J采用标志循环，终止循环的标志是：I、J、M三个的数字的位数和超过9（这个是本题的关键）。
在上述循环过程中， 当I，M，J三者的位数和等于9的时候，就判断，这9个位置上的
数字，是否刚好使用到1-9。 < br>也就是说在上述一一列举的过程中，并非需要都去检验，只有当满足正好是9位数字的
时候，去检 验。
问题：如何检验呢？

是符合要求的解，还有“135792468”也是符合要求的解。
通过数学分析知道，1- 9个数字的全排列，都是符合要求的解，显然用全排列的思路去
检验，是十分费时间的。
突然 想到，把这些符合要求的数字，按照升序排列，就只能是“123456789”，反之如
果9个数字中 有数字重复的就不等于“123456789”。
所以检验的算法如下：
1，把I、M、J三个数字转换成字符串，然后连接成一个字符串Lins。
2，把Lins用Split()函数，拆分保存到一个数组d()。
3，对数组d()，进行升序排列。
4，将排列后的数组d()，连接成新的字符串Lins。
5，最后进行检验判断。

二．算法思路：
（一）主程序的算法：
分析：有关系式：M = J *（N – I）
1．读取给出的N。
2．I = 1
3．如果I = N 就转向步骤11
4． J = 1，(J是分母)；M = J*（N - I）；W = I的位数 + J的位数 + M的位数
5． 如果 W > 9 就转向 9
6． If W = 9 Then
判断I，J，M三个数字是否正好使用1-9各一次；
如果是的：G = G + 1 ‘用G存放满足条件的个数
End If
7． J = J + 1；M = J*（N - I）；W = I的位数 + J的位数 + M的位数
8． 转向5
9． I = I + 1
10．转向3
11．输出 G

（二）检验I、J、M三个正整数是否正好使用1-9各1次的自定义函数的算法：
首先，从主程序里可以看到，此时I、J、M三个正整数的位数和为9。
1．个正整数I、J、M转换成字符串类型，把他们连接成一个字符串；

例如：I = 81，J = 297，M = 5643，得到字符串Lins = “812975643”
2．为了判断是否正好使用1-9各一次，方法肯定不是唯一，我的方法是：
把变量Lins里的字符，从小到大排列，排列后与”123456789”比较是否相等。
具体实现：利用VB6里的Split()函数，把这9个字符拆分到数组的9个元素里，再进< br>行升序排序，再连接成字符串。
3．如果比较结果一致，函数返回TRUE，反之函数返回FALSE。

以上就是整个算法的思路：

完整的代码：
窗体上添加一个文本框和一个按钮，文本框用来接受输入N的值。
Option Explicit

Private Sub Command1_Click()
Dim i As Long
Dim j As Long
Dim m As Long
Dim W As Integer
Dim N As Long
Dim G As Integer
d = False
G = 0
N = Val()
For i = 1 To N - 1
j = 2
m = j * (N - i)
W = Len(CStr(i)) + Len(CStr(j)) + Len(CStr(m))
Do While W <= 9
If W = 9 Then
'i是整数部分，j是分子，m是分母
If Jug(i, j, m) Then G = G + 1: i, j, m
End If
j = j + 1
m = j * (N - i)
W = Len(CStr(i)) + Len(CStr(j)) + Len(CStr(m))
Loop
Next i
Print G
d = True
End Sub

'判断是否满足条件--ii是整数部分，ji是分子，mm是分母
Private Function Jug(ByVal ii As Long, ByVal jj As Long, ByVal mm As Long) As Boolean
Dim Lins As String

Dim d(1 To 9) As Integer
Dim i As Integer
Dim j As Integer
Dim T As Integer
Lins = CStr(ii) & CStr(jj) & CStr(mm)
For i = 1 To 9
d(i) = Val(Mid(Lins, i, 1))
Next i
For i = 1 To 8
For j = i + 1 To 9
If d(i) > d(j) Then
T = d(i)
d(i) = d(j)
d(j) = T
End If
Next j
Next i
Lins =
For i = 1 To 9
Lins = Lins & CStr(d(i))
Next i
If Lins =
Jug = True
Else
Jug = False
End If
End Function

2013年12月17日