加载中…
个人资料
taigxi
taigxi
  • 博客等级:
  • 博客积分:0
  • 博客访问:2,115
  • 关注人气:1
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

快与慢.

(2011-07-18 03:23:08)
标签:

杂谈

a、老板让你最快的计算 f(N) = 13+23+…+N3。逐项计算当然是能够的,万一能直接算出来当然会大大加快电脑计算的速度。

切实上f(N) = (1+2+…+N)2 = N2*(N+1)2/4。

b、Josephus(约瑟夫)问题。这是个老生常谈的话题,疏忽如下:

已知n个人(以编号1,2,3...n离别表示)围坐在一张圆桌方圆。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌方圆的人全副出列。

法1,用循环链表。

法2,获得递推公式。t表示约瑟夫环中人数,J(t)表示在t人中的获胜者。

有n个人编号0、1、……、n-1,J(t) = (J(t-1) + m%t)%t = (J(t-1) + m)%t.,且J[1] = 0;最后收获为J[n] +k。

c、老板让你编个过程,以最快的速度计算50以下数的阶乘(例如15!)。万一过去遭到过这个问题可能思维精细,会在琢磨一些问题后能够写出一个过程,琢磨的问题前后有:

1、 依据阶乘的定义用一个迭代告终。当然你率先会琢磨到n!在n相当大的时候能够用stirling公式去接近,

____

n! ~ √ 2πn (n/e)n

很不幸这个类似公式在n-> +∞时切实值与类似值比值为1。不过你想起码能够用stirling来做测验类似验证算法是否准确。

2、然而即便是13!都超过了32位表白范围。因而不管是用迭代、直连接乘还是stirling都存在这个问题——上溢。你想到要组织一个自己的登记大数的构造

3、用数组吧。构造一个长度为m数组假想足够长能接受收获,数组的index从0到m的字节表示位权从20—2m-1。

2m-1

……

213

212

211

210

29

28

27

26

25

24

23

22

21

20

0

9

8

7

6

5

4

3

2

1

2

3

4

5

例如表格里的数表示9876543212345。(题外话,在这里想起一个比拟好玩的数111,111,1112 = 12345678987654321)

4、依据这个登记数据的构造,设计乘法垄断,例如对9876543212345 * 15,把15与每位的乘积保留,再加上上一位的进位,除以10的商用作下一位的进位;模10的收获作为这位的值。

unsigned int carry = 0u;

unsigned int mul = Num[i] * 15u + carry;

carry = mul/10u;

mul /= 10u;

Num[i] = mul;

还要计算数组究竟必需多大能力接受这个阶乘值。

n!≤ 10m;两旁取对数 log10n + log10 (n-1) +…+ log10 (2) ≤ m,对m做取顶垄断┌m┐,良好再加上1个字节,担心在取对数时会有渺小精度磨损。

5、过程写完后该当验证与切实收获是否合乎,于是你敞开matlab、mathematica可能os自带的计算器检讨,觉察收获准确。这时你才觉察已穿越了好几个钟头,黄花菜都凉了,而老板只是要你算很少几个数的阶乘。是的,你凡是用计算器算出收获告诉他就行,能够预先算出来硬联编到过程中,许多迅速算法都是相仿的建表的思路。(FFT)

建表只是假象,性质是更容易更打听地处理问题。我经常学了算法后反而笨手笨脚了。

Struts2 OGNL的分析与简介.

C# 中多态性.

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有