加关注

银河里的星星

日志

几个经典问题

2008-05-03 19:39:17|  分类： 思维训练 |  标签： |举报 |字号

下载LOFTER 我的照片书  |
。。。笔记
1.划分问题
点划分直线：f(n) = f(n-1) + 1
线划分平面：g(n) = g(n-1) + f(n-1)
平面划分空间：s(n) = s(n-1)+g(n-1)
具有相似的递推关心，n维空间的划分与n-1维空间相关。
2.8皇后问题
n后问题存在构造解，对于解的个数目前尚未存在定理，只能搜索
3.8数码
数码问题存在解的条件是：与逆序对相关，观察移动过程，计算时，把0看成一个元素，考虑交换两个元素时的逆序数变化，前后总是相差奇数个，故如果逆序数的变化与0元素曼哈顿变化奇偶一致，则说明可达。

4.过桥

5.数独

6.24点

7.1...n中数字0的个数

8.布尔表达式求值

9.Joseph问题

10.next permutation

11.二分查找的优化

12.名人问题

13.BM算法

14.等值首尾和（元素全为正）

15.杨氏矩阵的查找

16.表示为两数平芳和

17.排列组合生成

18.找零钱

19.最大方块1矩阵

20.和为0的段落

21.atint,inta

22.输出所有合法括号

23.最大连续和，积

24.最长递增序列

25.等量正负号段落

26.知道不知道

27.链表树栈队列

28.n！最后一个非零位

1) n!=2^i*3^j*5^k*7^l*...

2) 求2^(i-k) mod 10
i=n/2+n/2/2+n/2/2/2+...  k=n/5+n/5/5+n/5/5/5+...

2^5 mod 10 = 2, 2^6 mod 10 = 4, ...

3) f(n!) mod 10 = ((f(1) mod 10) * (f(2) mod 10) * ... * (f(n) mod 10)) － (b)

f(i) mod 10有1，3，7，9四种可能，若能得到f(i) mod 10, i=1..n中3，7，9的个数
(b)式化为：f(n!) mod 10 = (3^a mod 10)*(7^b mod 10)*(9^c mod 10) － (c)

4) 求(c)式中a, b, c的值

For this problem we provide output files for both data sets as well as three p
rograms. The first program is very simple but also very inefficient and can be
used to solve only easy data set. The second program runs in time O(N 3) wher
e N is number of digits of a input number. Since the difficult input data set
contained numbers with N=91 digits, it is possible to use this program for sol
ving it. There is still another, more efficient program working in time O(N 2)
, which we present as well.

The first program
Consider the number N! factored into product of powers of prime numbers. It me
ans N!=2i * 3j * 5k * 7l * ... Note, that for each N>1 the power i is greater
than k. It means, that the last non-zero digit of N! is the same as the last d
igit of N! / (2k * 5k). Therefore we can compute the result using the equation
:

(N! / (2k * 5k)) mod 10 = ((N! / (2i * 5k)) mod 10 * 2i-k mod 10) mod 10
Number i can be obtained easily - we will divide each a=1,2,...,N by 2 until t
he resulting number is not divisible by 2 and after each division we will add
one to the variable i. Number k can be obtained in the same manner. Let f(i) d
enotes the number which we obtain by dividing i by the 2a * 5b where a and b a
re the highest numbers such that the i is divisible by this product. Number (N
! / (2i * 5k)) mod 10 is equal to f(N!) mod 10 and can be computed as f(1) * f
(2) * ... * f(N) mod 10. We will perform operation mod 10 after each multiplic
ation in order to keep the resulting number as small as possible.

The advantege of this approach is that we do not need to implement arithmetics
of large numbers. Some ideas used here are used in the second, more efficient
program, as well.

The second program
The second program also computes the result as (2i-k mod 10 * f(N!) ) mod 10.
Numbers i and k are computed much more efficiently. More precisely

i=N div 2 + (N div 2) div 2 + ((N div 2) div 2) div 2 + ...
(We get zero after finite number of divisions.) Number k can be computed in th
e same way. After that we can compute i-k and we need to find 2i-k mod 10. Obs
erve, that

21 mod 10 = 2, 22 mod 10 = 4, 23 mod 10 = 8, 24 mod 10 = 6, 25 mod 10 = 2, 26
mod 10 = 4, ...
i.e. the period is 4 and we need only to compute (i-k) mod 4 and then to find
corresponding last digit. This observation can help us to simplify computation
of i and k - we do not need their exact values (that can be long) but we need
only (i-k) mod 4.

We have shown how to compute 2i-k mod 10. Now let us consider f(N!) mod 10 = (
(f(1) mod 10) * (f(2) mod 10) * ... * (f(N) mod 10)) mod 10. Note, that f(i) m
od 10 is always 1,3,7 or 9. If we knew, how many 3,7,9 are among (f(1) mod 10)
, (f(2) mod 10), ..., (f(N) mod 10), we could compute 3a mod 10, 7b mod 10, 9c
mod 10 in the similar way as we did for 2i-k (last digits of powers of 3,7,9
are also periodical).

To compute the number of 3,7,9 among (f(1) mod 10), (f(2) mod 10), ..., (f(N)
mod 10) is not so easy. We will divide numbers 1,2,...,N into groups so, that
in each group are numbers with same quotient i/f(i) and we will compute number
of 3,7,9 among (f(i) mod 10) for each such group separatelly (there are O(N2)
such groups). First, let us consider a group in which i/f(i)=1. This is the g
roup of all numbers not divisible by 2 and 5. The number of 3,7,9 in this grou
p is the same as number of 3,7,9 among 1 mod 10, 2 mod 10, ..., N mod 10. This
number can be counted easily - it is N div 10 + a where a is 1 if the last di
git of N is at least 3 (resp. at least 7 or at least 9). Now let us consider a
group in which i/f(i)=L (where L=2a * 5b). We obtain this group by taking eac
h L-th number from the sequence 1,2,3,... and dividing it by L. It means that
number of 3,7,9 for this group will be the same as the number of 3,7,9 among 1
mod 10, 2 mod 10, ..., (N div L) mod 10.

Now we know everything we needed for construction of a program. Since numbers
in the input file are long, we need to implement arithmetics for long numbers.
However, by careful implementation we can achieve that only division of a lon
g number by small integer is necessary.

The third program.
Description of the algorithm used in this program will be available later.
评论这张

评论

<#--最新日志，群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇，下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->