大数阶乘截断

题目来源

这是日本一个编程网站上的题，当时看别人介绍的时候，说每通过一道题，就可以给
动漫女性角色换一件衣服或装饰，这道题是比较难的，也是”奖励”最重的一道，做完基本
就通关了。话说这种方式还比较新颖，对那些死宅的程序员来说，诱惑很大。
若有兴趣，可以移步Get a girl friend in programing。

里面都是日文，我都是连蒙带猜才成功做到最后一题。

题目描述

0<=n<=1000000,求n!去除末尾所有0之后的后9位数字，其中9位数字中若以0开头,则去掉0,剩下的数字即为结果。
例如:

1
2
3
4
10!=3628800 => 去掉末尾0，变成36288
38!=523022617466601111760007224100074291200000000 
=> 去掉0,取9位数字，得到000742912，
=> 去掉开头的0,得到最后结果742912

解法历程

思路1.0

  • 一开始我的想法是用Python快速写出来，Python自带大数计算，内存有多大就支持多大的数计算，
    不用做转换或者其他的库，这也是很多科研学科使用的语言，比较容易上手。我的想法是:
    1. 利用math.factorial(n)得到完整的结果
    2. 将结果转换成字符串，去掉末尾的0
    3. 若剩余大于9位，截取字符串后9位
    4. 最后去掉开头的0，得到结果

这种解法大概是人看到的第一反应了。python2代码如下:

1
2
3
4
5
6
7
*--- coding:utf-8 ---
import math
if __name__ == '__main__':
    n=int(input())
    r=math.factorial(n)
    s=str(r).rstrip('0')
    print int(s[-9:])

是不是很简单，但是python写起来效率高，性能就差了，在我的服务器上到
n=100000性能就不行了，以下是测试结果:

1
2
服务器配置:E5-2620 2.00GHz
内存:16GB

fact10000

这种写法在OJ上肯定超时，需要换思路，并且换一门编译类型的语言。

思路2.0

  • 自己手动控制阶乘流程，一旦结果结尾有0产生，立即去掉。
  • 进一步改进，一旦乘数包含2和5因子，将出现次数记录下来，一个2抵消一个5，而不参与乘法，
    这样就不会有结尾0出现，最后再将剩余的2或者5还原结果，这样对中间数字有影响。
  • 对结果同样保留9位，去除开头的0

选定语言

解法和语言没有太大关系，主要是选择一个自己用的顺手的语言。

  • 考虑过使用c,但是它的大数需要自己定义成数组，然后模拟乘法去做，比较繁琐，可以备用到后期改写。
  • C++太复杂，写一部分调试可能就要花掉很多时间，暂时不考虑。
  • Java很久没碰了，语法也比较啰嗦，写起来估计效果和C的差不多。

可能我就是需要一个自带的大数运算，后来发现golang不错,google里的三位大牛创造的，
专门为了解决工程中的一些现有的问题而产生的，熟悉了一下语法，明显是在向C语言致敬(好像其中有写K&R那本书的作者)，
想做分布式系统时代的”C语言”,没有继承泛型，很容易上手，之后我会写博客讲讲Go。

golang实现这个思路后，我为了充分利用硬件，使用了goroutine采用类似map/reduce的算法，分段式计算阶乘，
这样计算用时要少一些，主要代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
package main

import (
	"fmt"
	"log"
	"math/big"
	"strconv"
	"strings"
	"sync"
	"time"
)

type Count struct {
	Two int64
}

func dropTwoAndFive(n int64, cnt *Count) int64 {
	for n%2 == 0 {
		n /= 2
		cnt.Two++
	}
	for n%5 == 0 {
		n /= 5
		cnt.Two--
	}
	return n
}

func Recover(n *big.Int, cnt *Count) {
	if cnt.Two > 0 {
		for cnt.Two > 0 {
			n = n.Mul(n, big.NewInt(2))
			cnt.Two--
		}

	} else if cnt.Two < 0 {
		for cnt.Two < 0 {
			n = n.Mul(n, big.NewInt(5))
			cnt.Two++
		}
	}
}

func fact(c chan<- *big.Int, begin, end int64, cnt *Count, wg *sync.WaitGroup) {
	defer wg.Done()
	f := big.NewInt(1)
	//start specail cond.
	if begin == 0 {
		begin = 1
	}
	if begin >= end {
		c <- f
		return
	}
	for i := begin; i < end; i++ {
		f = f.Mul(f, big.NewInt(dropTwoAndFive(i, cnt)))
	}
	c <- f
}

func Factorial(c chan int64, n int64, w *sync.WaitGroup) {
	//wait get result
	defer w.Done()
	var wg sync.WaitGroup
	NUM := int64(4)

	f := big.NewInt(1)

	per := n / NUM

	channels := make([]chan *big.Int, NUM+1)
	cnts := make([]Count, NUM+1)

	wg.Add(int(NUM + 1))
	for i := int64(0); i < NUM; i++ {
		channels[i] = make(chan *big.Int, 1)
		go fact(channels[i], i*per, (i+1)*per, &(cnts[i]), &wg)
	}

	channels[NUM] = make(chan *big.Int, 1)
	go fact(channels[NUM], NUM*per, n+1, &(cnts[NUM]), &wg)

	//wait all calc channel
	wg.Wait()

	//slice to get result
	done := 0
	for {
		select {
		case res, ok := <-channels[0]:
			if ok {
				//log.Printf("channel[%d]res:%v\n", 0, res)
				if res.Cmp(big.NewInt(1)) != 0 {
					f = f.Mul(f, res)
				}
				close(channels[0])
				done++
			}

		case res, ok := <-channels[1]:
			if ok {
				//log.Printf("channel[%d]res:%v\n", 1, res)
				if res.Cmp(big.NewInt(1)) != 0 {
					f = f.Mul(f, res)
				}
				close(channels[1])
				done++
			}

		case res, ok := <-channels[2]:
			if ok {
				//log.Printf("channel[%d]res:%v\n", 2, res)
				if res.Cmp(big.NewInt(1)) != 0 {
					f = f.Mul(f, res)
				}
				close(channels[2])
				done++
			}
		case res, ok := <-channels[3]:
			if ok {
				//log.Printf("channel[%d]res:%v\n", 3, res)
				if res.Cmp(big.NewInt(1)) != 0 {
					f = f.Mul(f, res)
				}
				close(channels[3])
				done++
			}
		case res, ok := <-channels[4]:
			if ok {
				//log.Printf("channel[%d]res:%v\n", 4, res)
				if res.Cmp(big.NewInt(1)) != 0 {
					f = f.Mul(f, res)
				}
				close(channels[4])
				done++
			}

		}
		if int64(done) == (NUM + 1) {
			break
		}
	}
	//recover
	sum := int64(0)
	for _, cnt := range cnts {
		sum += cnt.Two
	}
	//log.Println("sum(2):", sum, "\torigin:", f)

	Recover(f, &Count{sum})
	s := f.String()
	if len(s) > 9 {
		s = s[len(s)-9:]
	}
	result, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	c <- result
}

func TrimZero(n *big.Int) {
	s := strings.TrimRight(n.String(), "0")
	var ok bool
	n, ok = n.SetString(s, 10)
	if !ok {
		log.Fatal("convert failed!")
	}
}

func main() {
	n := int64(0)
	fmt.Scanln(&n)

	start := time.Now()
	var wg sync.WaitGroup
	wg.Add(1)
	//cnt := new(Count)
	c := make(chan int64, 1)
	//go fact(c, 1, n, cnt, &wg)
	go Factorial(c, n, &wg)
	wg.Wait()

	fmt.Println(<-c, "time:", time.Now().Sub(start).Seconds())
	close(c)
}

编译之后运行还是比较快的，测试的10000和100000如下:
gofact-10000

这种方式在网站上运行时只得了60分，超过3秒就超时，估计OJ系统用了上限去测试。
因此只能继续改进算法。

思路3.0

这种解法就是用一个9位的数组模拟乘法运算，继续之前丢掉0的策略，结果超出9位的
部分也丢掉，这样自然就很快了，但是实际测试的时候发现数字计算有的不对。

看来还要思考准确性的问题出在哪。

总结

写这篇博文只是做一个暂时性的总结，毕竟问题还没有达到要求。
因为这道题，我开始接触了golang,之前一直排斥这种怪异的语法，现在则看得开了，觉得
什么的场景合适什么特点的语言。

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:大数阶乘截断

文章作者:linghutf

发布时间:2016年01月09日 - 05时12分

最后更新:2016年02月28日 - 22时10分

原始链接:http://linghutf.gitcafe.io/2016/01/09/factor/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目来源
    1. 1.1. 里面都是日文，我都是连蒙带猜才成功做到最后一题。
  2. 2. 题目描述
  3. 3. 解法历程
    1. 3.1. 思路1.0
    2. 3.2. 这种写法在OJ上肯定超时，需要换思路，并且换一门编译类型的语言。
    3. 3.3. 思路2.0
      1. 3.3.1. 选定语言
    4. 3.4. 思路3.0
    5. 3.5. 看来还要思考准确性的问题出在哪。
  4. 4. 总结
,