|
|
2006年6月29日
第一個(gè)是遞歸版本的：（沒什么意思）
?
#include?
<
iostream
>
????
using
?
namespace
?std;?
void
?move(
char
?from,?
char
?to)?
 
{?
 ????cout?
<<
?from?
<<
?
"
?to?
"
?
<<
?to?
<<
?endl;?
 }
?
void
?hanoi?(
int
?n,?
char
?from,?
char
?to,?
char
?bridge)?
{?
????
if
(n?
==
?
1
)?
????????move(from,?to);?
????
else
?
  ????
{?
????????hanoi?(n
-
1
,?from,?bridge,?to);?
????????move(from?,bridge);?
????????hanoi?(n
-
1
,?bridge,?from,?to);?
 ????}
?
}
?
int
?main()?
{?
????
int
?n;?
???? cout?
<<
?
"
input?n:\n
"
;?
???? cin?
>>
?n;?
???? hanoi?(n,?
'
A
'
,?
'
C
'
,?
'
B
'
);?
????
return
?
0
;?
}
?
?
?
第二個(gè)是遞歸版本的：（沒有用棧，因此還比較精妙）
對(duì)不起，由于一時(shí)疏忽，把兩個(gè)版本的程序貼成同一個(gè)了，十分抱歉，謝謝您的提醒，現(xiàn)更正如下：
#include?
<
iostream
>
using
?
namespace
?std;
void
?hanoi(
int
?n)
{
?????
int
?i,?j,?f?
=
?
1
;
?????
int
?a?
=
?
1
,?b?
=
?(n
%
2
)
?
?
3
:
2
;
?????cout?
<<
?f?
<<
?
"
?from?
"
?
<<
?
char
(
'
A
'
?
-
?
1
?
+
?a)?
<<
?
"
?to?
"???
??????????????? <<?char('A'?-?1?+?b)?<<?endl;
?????for(n?=?(1<<n)?-?1,?i?=?1;?i?<?n;?i?+=?2)
?????{
???????????for(f?=?1,?j?=?i;?j%2;?j/=2,?f++);
???????????if(f%2)
??????????????????a?^=?b;
???????????b?^=?a;
???????????cout?<<?f?<<?"?from?"?<<?char('A'?-?1?+?a)?<<?"?to?"??
????????????????????? <<?char('A'?-?1?+?b)?<<?endl;
???????????a?^=?b;
???????????if(f%2)
??????????????????b?^=?a;
???????????cout?<<?f?<<?"?from?"?<<?char('A'?-?1?+?a)?<<?"?to?"??
???????????????????? ?<<?char('A'?-?1?+?b)?<<?endl;
?????}
}
int
?main()
{
????
int
?n;
????cout?
<<
?
"
input?n:?
"
;
????cin?
>>
?n;
????hanoi(n);
????
return
?
0
;
}
?
2006年6月28日
2006年6月21日
??? zz:程序員每天該做的事?
1、總結(jié)自己一天任務(wù)的完成情況?
最好的方式是寫工作日志，把自己今天完成了什么事情，遇見了什么問題都記錄下來，日后翻看好處多多?
2、考慮自己明天應(yīng)該做的主要工作?
把明天要做的事情列出來，并按照優(yōu)先級(jí)排列，第二天應(yīng)該把自己效率最高的時(shí)間分配給最重要的工作?
3、考慮自己一天工作中失誤的地方，并想出避免下一次再犯的方法?
出錯(cuò)不要緊，最重要的是不要重復(fù)犯相同的錯(cuò)誤，那是愚蠢?
4、考慮自己一天工作完成的質(zhì)量和效率能否還能提高?
一天只提高1%，365天你的效率就能提高多少倍你知道嗎？?(1+0.01)^365?=?37?倍?
5、看一個(gè)有用的新聞網(wǎng)站或讀一張有用的報(bào)紙，了解業(yè)界動(dòng)態(tài)?
閉門造車是不行的，了解一下別人都在做什么，對(duì)自己能帶來很多啟示?
6、記住一位同事的名字及其特點(diǎn)?
你認(rèn)識(shí)公司的所有同事嗎？你了解他們嗎？?
7、清理自己的代碼?
今天完成的代碼，把中間的調(diào)試信息，測(cè)試代碼清理掉，按照編碼風(fēng)格整理好，注釋都寫好了嗎？?
8、清理自己的桌面?
當(dāng)日事當(dāng)日畢，保持清潔干勁的桌面才能讓你工作時(shí)不分心，程序員特別要把電腦的桌面清理干凈?
程序員每周該做的事?
1、向你的老板匯報(bào)一次工作?
讓你的老板知道你在做什么，這很重要。可以口頭、書面、郵件，看你老板的工作方式而定?
2、進(jìn)行一次自我總結(jié)（非正式）?
這周之內(nèi)自己表現(xiàn)得怎么樣？該加分還是扣分？?
3、制定下周計(jì)劃?
把下周要做的事情列出來，一樣要分清楚優(yōu)先級(jí)?
4、整理自己的文件夾、書柜和電腦文件?
把桌面以外的地方也要清理干凈，電腦的文件夾，收到的郵件，把過時(shí)的垃圾全部清理掉?
5、與一個(gè)非公司的朋友溝通?
它山之石，可以攻玉?
6、看一本雜志?
找一本適合自己的專業(yè)雜志?
7、糾正自己或同事一個(gè)細(xì)節(jié)上的不正確做法?
《細(xì)節(jié)決定成敗》看過了嗎？沒看過強(qiáng)烈建議先看看?
程序員每月該做的事?
1、至少和一個(gè)同事一起吃飯或喝茶?
不光了解自己工作伙伴的工作，還要了解他們的生活?
2、自我考核一次?
相對(duì)正式地考核自己一下，你對(duì)得起這個(gè)月的工資嗎？?
3、對(duì)你的同事考核一次?
你的同事表現(xiàn)怎么樣？哪些人值得學(xué)習(xí)，哪些人需要幫助？?
4、制定下月的計(jì)劃，確定下月的工作重點(diǎn)?
5、總結(jié)自己工作質(zhì)量改進(jìn)狀況?
自己的質(zhì)量提高了多少？?
6、有針對(duì)性地對(duì)一項(xiàng)工作指標(biāo)做深入地分析并得出改進(jìn)的方案?
可以是對(duì)自己的，也可以是對(duì)公司的，一定要深入地分析后拿出自己的觀點(diǎn)來。要想在老板面前說得上話，做的成事，工作上功夫要做足。?
7、與老板溝通一次?
最好是面對(duì)面地溝通，好好表現(xiàn)一下自己，虛心聽取老板的意見，更重要的是要了解老板當(dāng)前關(guān)心的重點(diǎn)?
程序員每年該做的事?
1、年終總結(jié)?
每個(gè)公司都會(huì)做的事情，但你真正認(rèn)真地總結(jié)過自己?jiǎn)幔?
2、兌現(xiàn)給自己、給家人的承諾?
給老婆、兒子的新年禮物買了沒有？給自己的呢？?
3、下年度工作規(guī)劃?
好好想想自己明年的發(fā)展目標(biāo)，爭(zhēng)取升職/加薪、跳槽還是自己出來干？?
4、掌握一項(xiàng)新技術(shù)?
至少是一項(xiàng)，作為程序員一年要是一項(xiàng)新技術(shù)都學(xué)不到手，那就一定會(huì)被淘汰。?
掌握可不是看本書就行的，要真正懂得應(yīng)用，最好你能夠?qū)懸黄坛贪l(fā)表到你的blog?
5、推出一種新產(chǎn)品?
可以是一個(gè)真正的產(chǎn)品，也可以只是一個(gè)類庫，只要是你創(chuàng)造的東西就行，讓別人使用它，也為世界作點(diǎn)貢獻(xiàn)。當(dāng)然如果真的很有價(jià)值，收點(diǎn)注冊(cè)費(fèi)也是應(yīng)該的?
6、與父母團(tuán)聚一次?
?；丶铱纯矗；丶铱纯?
2006年6月20日
??? ??? 1、注意勞逸結(jié)合，防止肌腱勞損。長時(shí)間操作電腦會(huì)導(dǎo)致手指關(guān)節(jié)、手腕、手臂肌肉、雙肩、頸部、背部等部位出現(xiàn)酸脹疼痛，因此，操作者在工作一小時(shí)后應(yīng)休息10分鐘，或者做做工間操。 2、要注意用眼衛(wèi)生。眼睛與文稿、眼睛與屏幕的距離應(yīng)保持在50厘米以上，最好采用光下視20度的視角。工作時(shí)，應(yīng)在面部及雙手涂抹防輻射的護(hù)膚油。 3、孕婦每周接觸電腦時(shí)間不超過20小時(shí)。要防止長時(shí)間坐位引起盆腔血液滯留不暢，做到張馳有度；要注意電腦與座椅坐姿的高低配合，讓胎兒健康發(fā)育。
4、長期從事電腦操作者，應(yīng)多吃一些新鮮的蔬菜和水果。同時(shí)增加維生素A、B1、C、E的攝入。為預(yù)防角膜干燥、眼干澀、視力下降、甚至出現(xiàn)夜盲癥等，
電腦操作者應(yīng)多吃些富含維生素A的食物，如豆制口、魚、牛奶、核桃、青菜、大白菜，西紅柿、空心菜及新鮮水果等。維生素C可以有效地抑制細(xì)胞氧化。維生素
E主要作用是：降低膽固醇，清除身體內(nèi)垃圾，預(yù)防白內(nèi)障。核桃和花生中含有豐富的維生素E。維生素B1可以加強(qiáng)神經(jīng)細(xì)胞的營養(yǎng)，緩解神經(jīng)的緊張狀態(tài)。 5、每天泡點(diǎn)綠茶。茶葉中的脂多糖，可改善肌體造血工能。人體注入脂多糖后，在短時(shí)間內(nèi)即可增強(qiáng)機(jī)體非特異性免疫力。茶葉還能防輻射損害。 6、為了避免熒光屏反光或不清晰，電腦不應(yīng)放置在窗戶的對(duì)面或背面；環(huán)境照明要柔和，如果操作者身后有窗戶應(yīng)拉上窗簾，避免亮光直接照射到屏幕上反向出明亮的影像造成眼部的疲勞。 7、電腦房間要經(jīng)常通風(fēng)，在室內(nèi)安裝換氣扇或空調(diào)，減輕溴比二苯呋喃對(duì)身體的影響。計(jì)算機(jī)附近的灰塵密度要比機(jī)房其它空間高出上百倍，它們長時(shí)間附著于人的皮膚上，可導(dǎo)致各類皮膚病。電腦房間要保持清潔衛(wèi)生，電腦要定期擦洗。 8、一般人每分鐘眨眼少于5次會(huì)使眼睛干燥。一個(gè)人在電腦工作時(shí)眨睛次數(shù)只及平時(shí)的三分之一，因而減少了眼內(nèi)潤滑劑和酶的分泌。應(yīng)該多眨眼，每隔一小時(shí)至少讓眼睛休息一次。
2006年6月16日
??? In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), .... For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97. Write a program to output all positive self-numbers less than 10000 in increasing order, one per line. Output1
3
5
7
9
20
31
42
53
64
|
| <-- a lot more numbers
|
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993
Solution#include?<iostream>
using?namespace?std;
const?long?N?=?10000;?????//最大自然數(shù)
char?Arr[N?+?9*4]={0};???//是否是被排除的數(shù)字？?+9*4是為了要再多放4位數(shù)
long?DealNum(long?n)
{
??long?sum?=?n;
??while?(n?!=?0)
??{
????sum?+=?n%10;
????n?/=?10;
??}
??return?sum;
}
int?main()
{
??int?i;
??for(i?=?1;?i?<?N;?i++)
??{
????Arr[DealNum(i)]?=?1;
??}
??for(i?=?1;?i?<?N;?i++)
??{
????if?(!Arr[i])
????????cout<<i<<endl;
??}
??return?0;
}
??? When printing out a document, normally the first page is printed first, then the second, then the third, and so on until the end. However, when creating a fold-over booklet, the order of printing must be altered. A fold-over booklet has four pages per sheet, with two on the front and two on the back. When you stack all the sheets in order, then fold the booklet in half, the pages appear in the correct order as in a regular book. For example, a 4-page booklet would print on 1 sheet of paper: the front will contain page 4 then page 1, and the back will contain page 2 then page 3. Front Back
------------- -------------
| | | | | |
| 4 | 1 | | 2 | 3 |
| | | | | |
------------- -------------
Your task is to write a program that takes as input the number of pages to be printed, then generates the printing order. The input file contains one or more test cases, followed by a line containing the number 0 that indicates the end of the file.
Each test case consists of a positive integer n on a line by itself, where n is the number of pages to be printed; n will not exceed 100. For each test case, output a report indicating which pages should be printed on each sheet, exactly as shown in the example. If the desired number of pages does not completely fill up a sheet, then print the word Blank in place of a number. If the front or back of a sheet is entirely blank, do not generate output for that side of the sheet.
Output must be in ascending order by sheet, front first, then back. 1
14
4
0
Printing order for 1 pages:
Sheet 1, front: Blank, 1
Printing order for 14 pages:
Sheet 1, front: Blank, 1
Sheet 1, back : 2, Blank
Sheet 2, front: 14, 3
Sheet 2, back : 4, 13
Sheet 3, front: 12, 5
Sheet 3, back : 6, 11
Sheet 4, front: 10, 7
Sheet 4, back : 8, 9
Printing order for 4 pages:
Sheet 1, front: 4, 1
Sheet 1, back : 2, 3
#include?<iostream>
using?namespace?std;
#define?PAGES?100
typedef?struct?side{????
????int?left,right;
}side;
typedef?struct?sheet{
????side?front;
????side?back;????
}sheet;
int?numSides;
sheet?sheets[PAGES];
void?PrintPages(int?numSides){
????int?numSidesNew;????
????int?add,pages;
????add?=?numSides%4;
????if(add?!=?0){
????????numSidesNew?=?numSides?+?4?-?add;????//?增加后的總面數(shù),numSides為實(shí)際的總面數(shù)
????}
????else
????????numSidesNew?=?numSides;
????pages?=?numSidesNew?/?4;????//?總紙張數(shù)
????for(int?i?=?0;?i?<?pages;?i++){
????????sheets[i].front.left?=?numSidesNew?-?2*i;
????????if(sheets[i].front.left?>?numSides){
????????????sheets[i].front.left?=?0;????//?表明應(yīng)為blank
????????}
????????sheets[i].front.right?=?2*i+1;
????????if(sheets[i].front.right?>?numSides){
????????????sheets[i].front.right?=?0;????//?表明應(yīng)為blank
????????}
????????sheets[i].back.left?=?2*(i+1);
????????if(sheets[i].back.left?>?numSides){
????????????sheets[i].back.left?=?0;????//?表明應(yīng)為blank
????????}
????????sheets[i].back.right?=?numSidesNew?-?2*i?-?1;
????????if(sheets[i].back.right?>?numSides){
????????????sheets[i].back.right?=?0;
????????}
????}
????cout?<<?"Printing?order?for?"?<<?numSides?<<?"?pages:"?<<?endl;
????for(int?j?=?0;?j?<?pages;?j++){
????????if(sheets[j].front.left?||?sheets[j].front.right){
????????????cout?<<?"Sheet?"?<<?j+1?<<",?front:?";
????????????if(sheets[j].front.left)
????????????????cout?<<?sheets[j].front.left?<<?",";
????????????else
????????????????cout?<<?"Blank,";
????????????cout?<<?"?";
????????????if(sheets[j].front.right)
????????????????cout?<<?sheets[j].front.right;
????????????else
????????????????cout?<<?"Blank,";
????????????cout?<<?endl;
????????}
????????if(sheets[j].back.left?||?sheets[j].back.right){
????????????cout?<<?"Sheet?"?<<?j+1?<<",?back?:?";
????????????if(sheets[j].back.left)
????????????????cout?<<?sheets[j].back.left?<<?",";
????????????else
????????????????cout?<<?"Blank,";
????????????cout?<<?"?";
????????????if(sheets[j].back.right)
????????????????cout?<<?sheets[j].back.right;
????????????else
????????????????cout?<<?"Blank";
????????????cout?<<?endl;
????????}
????}
}
int?main()
{
????int?numSides;
????while(cin?>>?numSides){
????????if(numSides?==?0){
????????????break;
????????}
????????PrintPages(numSides);
????}
????return?0;
}
http://bbs.gameres.com/showthread.asp?threadid=46513
日前在書上看到一段使用多項(xiàng)式逼近計(jì)算平方根的代碼，至今都沒搞明白作者是怎樣推
算出那個(gè)公式的。但在嘗試解決問題的過程中，學(xué)到了不少東西，于是便有了這篇心
得，寫出來和大家共享。其中有錯(cuò)漏的地方，還請(qǐng)大家多多指教。
的確，正如許多人所說的那樣，現(xiàn)在有有FPU，有3DNow，有SIMD，討論軟件算法好像不
合時(shí)宜。關(guān)于sqrt的話題其實(shí)早在2003年便已在?GameDev.net上得到了廣泛的討論（可
見我實(shí)在非?；鹦橇?，當(dāng)然不排除還有其他尚在冥王星的人，嘿嘿）。而嘗試探究該話
題則完全是出于本人的興趣和好奇心（換句話說就是無知）。
我只是個(gè)beginner，所以這種大是大非的問題我也說不清楚（在GameDev.net上也有很多
類似的爭(zhēng)論）。但無論如何，Carmack在DOOM3中還是使用了軟件算法，而多知道一點(diǎn)數(shù)
學(xué)知識(shí)對(duì)3D編程來說也只有好處沒壞處。3D圖形編程其實(shí)就是數(shù)學(xué)，數(shù)學(xué)，還是數(shù)學(xué)。
文章原本是用HTML編排的，所以只截取了部分有比較有趣的東西放在這里。原文在我的
個(gè)人主頁上，同時(shí)也提供了2篇論文的下載：http:
//greatsorcerer.go2.icpcn.com/info/fastsqrt.html
=========================================================
在3D圖形編程中，經(jīng)常要求平方根或平方根的倒數(shù)，例如：求向量的長度或?qū)⑾蛄繗w一
化。C數(shù)學(xué)函數(shù)庫中的sqrt具有理想的精度，但對(duì)于3D游戲程式來說速度太慢。我們希望
能夠在保證足夠的精度的同時(shí)，進(jìn)一步提高速度。
Carmack在QUAKE3中使用了下面的算法，它第一次在公眾場(chǎng)合出現(xiàn)的時(shí)候，幾乎震住了所
有的人。據(jù)說該算法其實(shí)并不是Carmack發(fā)明的，它真正的作者是Nvidia的Gary?Tarolli
（未經(jīng)證實(shí)）。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
//?計(jì)算參數(shù)x的平方根的倒數(shù)
//
float?InvSqrt?(float?x)
{
float?xhalf?=?0.5f*x;
int?i?=?*(int*)&x;
i?=?0x5f3759df?-?(i?>>?1);?//?計(jì)算第一個(gè)近似根
x?=?*(float*)&i;
x?=?x*(1.5f?-?xhalf*x*x);?//?牛頓迭代法
return?x;
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
該算法的本質(zhì)其實(shí)就是牛頓迭代法（Newton-Raphson?Method，簡(jiǎn)稱NR），而NR的基礎(chǔ)則
是泰勒級(jí)數(shù)（Taylor?Series）。NR是一種求方程的近似根的方法。首先要估計(jì)一個(gè)與方
程的根比較靠近的數(shù)值，然后根據(jù)公式推算下一個(gè)更加近似的數(shù)值，不斷重復(fù)直到可以
獲得滿意的精度。其公式如下：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
函數(shù)：y=f(x)
其一階導(dǎo)數(shù)為：y'=f'(x)
則方程：f(x)=0?的第n+1個(gè)近似根為
x[n+1]?=?x[n]?-?f(x[n])?/?f'(x[n])
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
NR最關(guān)鍵的地方在于估計(jì)第一個(gè)近似根。如果該近似根與真根足夠靠近的話，那么只需
要少數(shù)幾次迭代，就可以得到滿意的解。
現(xiàn)在回過頭來看看如何利用牛頓法來解決我們的問題。求平方根的倒數(shù)，實(shí)際就是求方
程1/(x^2)-a=0的解。將該方程按牛頓迭代法的公式展開為：
x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])
將1/2放到括號(hào)里面，就得到了上面那個(gè)函數(shù)的倒數(shù)第二行。
接著，我們要設(shè)法估計(jì)第一個(gè)近似根。這也是上面的函數(shù)最神奇的地方。它通過某種方
法算出了一個(gè)與真根非常接近的近似根，因此它只需要使用一次迭代過程就獲得了較滿
意的解。它是怎樣做到的呢？所有的奧妙就在于這一行：
i?=?0x5f3759df?-?(i?>>?1);?//?計(jì)算第一個(gè)近似根
超級(jí)莫名其妙的語句，不是嗎？但仔細(xì)想一下的話，還是可以理解的。我們知道，IEEE
標(biāo)準(zhǔn)下，float類型的數(shù)據(jù)在32位系統(tǒng)上是這樣表示的（大體來說就是這樣，但省略了很
多細(xì)節(jié)，有興趣可以GOOGLE）：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
bits：31?30?...?0
31：符號(hào)位
30-23：共8位，保存指數(shù)（E）
22-0：共23位，保存尾數(shù)（M）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
所以，32位的浮點(diǎn)數(shù)用十進(jìn)制實(shí)數(shù)表示就是：M*2^E。開根然后倒數(shù)就是：M^(-1/2)*2^
(-E/2)。現(xiàn)在就十分清晰了。語句i>?>1其工作就是將指數(shù)除以2，實(shí)現(xiàn)2^(E/2)的部分。
而前面用一個(gè)常數(shù)減去它，目的就是得到M^(1/2)同時(shí)反轉(zhuǎn)所有指數(shù)的符號(hào)。
至于那個(gè)0x5f3759df，呃，我只能說，的確是一個(gè)超級(jí)的Magic?Number。
那個(gè)Magic?Number是可以推導(dǎo)出來的，但我并不打算在這里討論，因?yàn)閷?shí)在太繁瑣了。
簡(jiǎn)單來說，其原理如下：因?yàn)镮EEE的浮點(diǎn)數(shù)中，尾數(shù)M省略了最前面的1，所以實(shí)際的尾
數(shù)是1+M。如果你在大學(xué)上數(shù)學(xué)課沒有打瞌睡的話，那么當(dāng)你看到(1+M)^(-1/2)這樣的形
式時(shí)，應(yīng)該會(huì)馬上聯(lián)想的到它的泰勒級(jí)數(shù)展開，而該展開式的第一項(xiàng)就是常數(shù)。下面給
出簡(jiǎn)單的推導(dǎo)過程：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
對(duì)于實(shí)數(shù)R>0，假設(shè)其在IEEE的浮點(diǎn)表示中，
指數(shù)為E，尾數(shù)為M，則：
R^(-1/2)
=?(1+M)^(-1/2)?*?2^(-E/2)
將(1+M)^(-1/2)按泰勒級(jí)數(shù)展開，取第一項(xiàng)，得：
原式
=?(1-M/2)?*?2^(-E/2)
=?2^(-E/2)?-?(M/2)?*?2^(-E/2)
如果不考慮指數(shù)的符號(hào)的話，
(M/2)*2^(E/2)正是(R>>1)，
而在IEEE表示中，指數(shù)的符號(hào)只需簡(jiǎn)單地加上一個(gè)偏移即可，
而式子的前半部分剛好是個(gè)常數(shù)，所以原式可以轉(zhuǎn)化為：
原式?=?C?-?(M/2)*2^(E/2)?=?C?-?(R>>1)，其中C為常數(shù)
所以只需要解方程：
R^(-1/2)
=?(1+M)^(-1/2)?*?2^(-E/2)
=?C?-?(R>>1)
求出令到相對(duì)誤差最小的C值就可以了
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
上面的推導(dǎo)過程只是我個(gè)人的理解，并未得到證實(shí)。而Chris?Lomont則在他的論文中詳
細(xì)討論了最后那個(gè)方程的解法，并嘗試在實(shí)際的機(jī)器上尋找最佳的常數(shù)C。有興趣的朋友
可以在文末找到他的論文的鏈接。
所以，所謂的Magic?Number，并不是從N元宇宙的某個(gè)星系由于時(shí)空扭曲而掉到地球上
的，而是幾百年前就有的數(shù)學(xué)理論。只要熟悉NR和泰勒級(jí)數(shù)，你我同樣有能力作出類似
的優(yōu)化。
在GameDev.net?上有人做過測(cè)試，該函數(shù)的相對(duì)誤差約為0.177585%，速度比C標(biāo)準(zhǔn)庫的
sqrt提高超過20%。如果增加一次迭代過程，相對(duì)誤差可以降低到e-?004?的級(jí)數(shù)，但速
度也會(huì)降到和sqrt差不多。據(jù)說在DOOM3中，Carmack通過查找表進(jìn)一步優(yōu)化了該算法，
精度近乎完美，而且速度也比原版提高了一截（正在努力弄源碼，誰有發(fā)我一份）。
值得注意的是，在Chris?Lomont的演算中，理論上最優(yōu)秀的常數(shù)（精度最高）是
0x5f37642f，并且在實(shí)際測(cè)試中，如果只使用一次迭代的話，其效果也是最好的。但奇
怪的是，經(jīng)過兩次NR后，在該常數(shù)下解的精度將降低得非常厲害（天知道是怎么回
事?。?。經(jīng)過實(shí)際的測(cè)試，Chris?Lomont認(rèn)為，最優(yōu)秀的常數(shù)是0x5f375a86。如果換成
64位的double版本的話，算法還是一樣的，而最優(yōu)常數(shù)則為?0x5fe6ec85e7de30da（又一
個(gè)令人冒汗的Magic?Number?-?-b）。
這個(gè)算法依賴于浮點(diǎn)數(shù)的內(nèi)部表示和字節(jié)順序，所以是不具移植性的。如果放到Mac上跑
就會(huì)掛掉。如果想具備可移植性，還是乖乖用sqrt好了。但算法思想是通用的。大家可
以嘗試推算一下相應(yīng)的平方根算法。
下面給出Carmack在QUAKE3中使用的平方根算法。Carmack已經(jīng)將QUAKE3的所有源代碼捐
給開源了，所以大家可以放心使用，不用擔(dān)心會(huì)受到律師信。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
//?Carmack在QUAKE3中使用的計(jì)算平方根的函數(shù)
//
float?CarmSqrt(float?x){
union{
int?intPart;
float?floatPart;
}?convertor;
union{
int?intPart;
float?floatPart;
}?convertor2;
convertor.floatPart?=?x;
convertor2.floatPart?=?x;
convertor.intPart?=?0x1FBCF800?+?(convertor.intPart?>>?1);
convertor2.intPart?=?0x5f3759df?-?(convertor2.intPart?>>?1);
return?0.5f*(convertor.floatPart?+?(x?*?convertor2.floatPart));
}
2006年6月10日
摘要: Background?
Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block worl... 閱讀全文
The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defined by the recurrence:
Write a program to calculate the Fibonacci Numbers.
The input to your program would be a sequence of numbers smaller or equal than 5000, each on a separate line, specifying which Fibonacci number to calculate.
Your program should output the Fibonacci number for each input value, one per line.
5
7
11
The Fibonacci number for 5 is 5
The Fibonacci number for 7 is 13
The Fibonacci number for 11 is 89
#include
<iostream>
using
namespace
std;
?
int
main()
{
??
int
first,next,temp,n;
??
while(cin >> n) {
?????
first = 0;
?????
next = 1;
?????
temp = 0;
?????
if(n == 0 || n == 1) {
???????
cout << "The Fibonacci number for" << " " << n << " " << "is" << " " << n << endl;
????? }
?????
else {
???????
for(inti = 2; i <= n; i++) {
??????????
temp = first + next;
??????????
first = next;
??????????
next = temp;
??????? }
???????
cout << "The Fibonacci number for" << " " << n << " " << "is" << " " << temp << endl;
????? }
?? }
??
return 0;
}
Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then tex2html_wrap_inline44
5. else tex2html_wrap_inline46
6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no opperation overflows a 32-bit integer.
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).
1 10
100 200
201 210
900 1000
1 10 20
100 200 125
201 210 89
900 1000 174
#include
<iostream>
using
namespace
std;
?
int
cycle(intm)
{
??
int
i = 1;
??
while (m != 1){
?????
if(m%2)
???????
m = m*3 + 1;
?????
else
???????
m /= 2;
?????
i++;
?? }
??
return
i;
}??
?
int
main()
{
??
int
m,n,max,temp;
??
int
mOriginal,nOriginal;
??
int
i;
?
??
while (cin >> m >> n){
?????
mOriginal = m;
?????
nOriginal = n;
?????
if (m > n){
???????
temp = m;
???????
m = n;
???????
n = temp;
????? }
?
?????
max = cycle(m);
?????
for (i = m+1; i <= n; i++){
???????
temp = cycle(i);
???????
if (temp > max){
??????????
max = temp;
??????? }
????? }?
?????
cout << mOriginal << " " << nOriginal << " " << max << endl;
?? }
??
return 0;
}
|