[20151010]从阶乘想到的.txt
--这个是不久以前遇到的事情,路过一个给中学生的兴趣班,老师讲编程如何实现1到10的阶乘累加。
--实际上这个问题并不难对于学过编程的人来讲,我想很久以前读高中老师也给我们讲解过这个问题。我记得老师还叫我上黑板写代码。
--我还记得下课时老师留下问题如何显示1到100的阶乘累加,实际上原来的算法就不行了,结果已经溢出。
--如果换到现在我会选择使用bc来实现。
--写一个脚本实现1到X的阶乘累加:
--随手写一个bc脚本:(注实际阶乘的代码来自man bc手册)
define f (x) {
if (x <= 1) return (1);
return (f(x-1) * x);
}
define g(x)
{
v=0;
for (i=1;i<=x;i++)
{
v=v+f(i);
}
return v;
}
g(1000);
--顺便计算一下1到1000的阶乘累加:
$ time cat aa.txt|bc
....
real 0m9.554s
user 0m9.550s
sys 0m0.004s
--结果需要大约10秒。这个时候我想起来当时写的代码非常类似的,除了没有使用递归。实际上当时老师给了另外的思路,就是先算
--X的阶乘,然后在不断的除来累加。更改后的代码如下:
$ cat ax.txt
define f (x) {
if (x <= 1) return (1);
return (f(x-1) * x);
}
define g(x)
{
v=0;
a=f(x);
for (i=x;i>=1;i--)
{
v+=a;
a/=i;
}
return v;
}
g(1000);
$ time cat ax.txt|bc
40279005053122345768067055829218304493044109455152896641933464292007\
59023700825508498789380111228748403226643957277673191284838468927263\
98968790560901035018977865543415443376965144616549510538851077440410\
16581978207347558308207939650411138088491681076846747131716891318394\
82758974908036466987938461908525944177396717869145634721620931809562\
84720843607311204509397095907530114810381703803860648328656344389023\
07797564774862888681746680472485858774784093678446243617397742999118\
27532073023480165384946420013014323952797267455381787277085030908707\
45742249581124437084158031806471602854863650302741825130214652788342\
62128387017583390657265689010443241309517109572355085104736018270081\
76664478334500979289573868762717655541374071117476665123099806785398\
86786878262902584539118231519316835523885400137767203426696953126303\
29282822423534913463028008448006465049776475547382410225945312773007\
77775310631151387649525275970984453800464439975409258800869363179334\
21768424925084707414812932329166745886234137226923024813461900363225\
99946452493522794764716794743441163713920351740437121423299823949395\
45623233270769039159314433053699628563882650273461556233325433029434\
46674383336900484885947609695640139797208838438493998636482572950930\
77791964440615462408422804298527057377454368956529809230106268980768\
90711203175785101421818927982471990714520220291727074006887589803057\
02923813291544851703914211657597582497807598793035565731652297925769\
88654916845086709116386840244201837134102214334904094189742237793154\
01317123760884519266468022552657218203325644539610917924487108866748\
97251899281432897966817352381951694370184383299109654078410356489144\
96097727448032065520547484257131085876715457907964421551419900383259\
92326310206845282039558131111404730746868104260513228920636501228410\
04997271652977702547274337834459757112850838135183696311712170990224\
73992869769477285314047680203373559457470718994182065679361157280067\
19481311281095580123586794462594962441430219979368012738883931024129\
18463505832701613704464047394891693567824946365095976820092895872874\
83306734547239954921373656827788157415912067076521596246358718445543\
39227025068139536377423837689642266483656100701688393247498969109923\
90804658988479107678562550844858514512762455637677863067821690083222\
83440561338870911918871947918152819083688890815284572902151349165858\
65098894556135702731215416389951458945610799992135000761012487815006\
42979091198044736325729107144579768273776743716439557581557253878204\
64739117658285116731218202618879515662005685650334009224747947868473\
8621107994804323593105039052556442336528920420940313
real 0m0.167s
user 0m0.165s
sys 0m0.002s
--不到0.2秒。
--可以发现算法实际上还是非常重要的,看看现在的开发,我觉得许多编程人员丢掉了许多东西,现在的机器cpu主频越快,我在单位最
--快的机器测试也需要3秒到4秒。看看他们写的sql语句真的很失望,我曾经说过如果让我看其它代码,能发现的问题更多............
--补充不断相乘呢?
$ cat ay.txt
define f (x) {
if (x <= 1) return (1);
return (f(x-1) * x);
}
define g(x)
{
v=0;
a=f(1);
for (i=2;i<=x;i++)
{
v+=a;
a*=i;
}
return v;
}
g(1000);
$ time cat ay.txt|bc
real 0m0.046s
user 0m0.043s
sys 0m0.003s
--这样更快。