技術(shù)，瞎侃，健康，休閑……

第一個是遞歸版本的：（沒什么意思）

?

?

?

第二個是遞歸版本的：（沒有用棧，因此還比較精妙）

對不起，由于一時疏忽，把兩個版本的程序貼成同一個了，十分抱歉，謝謝您的提醒，現(xiàn)更正如下：

?

在水木上見到一個貼子，關(guān)于虛函數(shù)的訪問權(quán)限問題：

其實這是一個關(guān)于訪問權(quán)限決定時間的問題，由于訪問權(quán)限是編譯時間決定的，而不是運行時決定的。
B *bp = new D;??// 此時bp所指向的類型是B而不是D，而B的f3()是公有的，所以可以訪問。
D *dp = new D; // 此時dp所指向的類型是D，而D的f3()是私有的，所以不能訪問。

??? zz:程序員每天該做的事?
1、總結(jié)自己一天任務(wù)的完成情況?
最好的方式是寫工作日志，把自己今天完成了什么事情，遇見了什么問題都記錄下來，日后翻看好處多多?

2、考慮自己明天應(yīng)該做的主要工作?
把明天要做的事情列出來，并按照優(yōu)先級排列，第二天應(yīng)該把自己效率最高的時間分配給最重要的工作?

3、考慮自己一天工作中失誤的地方，并想出避免下一次再犯的方法?
出錯不要緊，最重要的是不要重復(fù)犯相同的錯誤，那是愚蠢?

4、考慮自己一天工作完成的質(zhì)量和效率能否還能提高?
一天只提高1%，365天你的效率就能提高多少倍你知道嗎？?(1+0.01)^365?=?37?倍?

5、看一個有用的新聞網(wǎng)站或讀一張有用的報紙，了解業(yè)界動態(tài)?
閉門造車是不行的，了解一下別人都在做什么，對自己能帶來很多啟示?

6、記住一位同事的名字及其特點?
你認(rèn)識公司的所有同事嗎？你了解他們嗎？?

7、清理自己的代碼?
今天完成的代碼，把中間的調(diào)試信息，測試代碼清理掉，按照編碼風(fēng)格整理好，注釋都寫好了嗎？?

8、清理自己的桌面?
當(dāng)日事當(dāng)日畢，保持清潔干勁的桌面才能讓你工作時不分心，程序員特別要把電腦的桌面清理干凈?

程序員每周該做的事?
1、向你的老板匯報一次工作?
讓你的老板知道你在做什么，這很重要。可以口頭、書面、郵件，看你老板的工作方式而定?

2、進(jìn)行一次自我總結(jié)（非正式）?
這周之內(nèi)自己表現(xiàn)得怎么樣？該加分還是扣分？?

3、制定下周計劃?
把下周要做的事情列出來，一樣要分清楚優(yōu)先級?

4、整理自己的文件夾、書柜和電腦文件?
把桌面以外的地方也要清理干凈，電腦的文件夾，收到的郵件，把過時的垃圾全部清理掉?

5、與一個非公司的朋友溝通?
它山之石，可以攻玉?

6、看一本雜志?
找一本適合自己的專業(yè)雜志?

7、糾正自己或同事一個細(xì)節(jié)上的不正確做法?
《細(xì)節(jié)決定成敗》看過了嗎？沒看過強烈建議先看看?

程序員每月該做的事?
1、至少和一個同事一起吃飯或喝茶?
不光了解自己工作伙伴的工作，還要了解他們的生活?

2、自我考核一次?
相對正式地考核自己一下，你對得起這個月的工資嗎？?

3、對你的同事考核一次?
你的同事表現(xiàn)怎么樣？哪些人值得學(xué)習(xí)，哪些人需要幫助？?

4、制定下月的計劃，確定下月的工作重點?

5、總結(jié)自己工作質(zhì)量改進(jìn)狀況?
自己的質(zhì)量提高了多少？?

6、有針對性地對一項工作指標(biāo)做深入地分析并得出改進(jìn)的方案?
可以是對自己的，也可以是對公司的，一定要深入地分析后拿出自己的觀點來。要想在老板面前說得上話，做的成事，工作上功夫要做足。?

7、與老板溝通一次?
最好是面對面地溝通，好好表現(xiàn)一下自己，虛心聽取老板的意見，更重要的是要了解老板當(dāng)前關(guān)心的重點?

程序員每年該做的事?
1、年終總結(jié)?
每個公司都會做的事情，但你真正認(rèn)真地總結(jié)過自己嗎？?

2、兌現(xiàn)給自己、給家人的承諾?
給老婆、兒子的新年禮物買了沒有？給自己的呢？?

3、下年度工作規(guī)劃?
好好想想自己明年的發(fā)展目標(biāo)，爭取升職/加薪、跳槽還是自己出來干？?

4、掌握一項新技術(shù)?
至少是一項，作為程序員一年要是一項新技術(shù)都學(xué)不到手，那就一定會被淘汰。?
掌握可不是看本書就行的，要真正懂得應(yīng)用，最好你能夠?qū)懸黄坛贪l(fā)表到你的blog?

5、推出一種新產(chǎn)品?
可以是一個真正的產(chǎn)品，也可以只是一個類庫，只要是你創(chuàng)造的東西就行，讓別人使用它，也為世界作點貢獻(xiàn)。當(dāng)然如果真的很有價值，收點注冊費也是應(yīng)該的?

6、與父母團(tuán)聚一次?
常回家看看，常回家看看

???

??? 1、注意勞逸結(jié)合，防止肌腱勞損。長時間操作電腦會導(dǎo)致手指關(guān)節(jié)、手腕、手臂肌肉、雙肩、頸部、背部等部位出現(xiàn)酸脹疼痛，因此，操作者在工作一小時后應(yīng)休息10分鐘，或者做做工間操。

　　2、要注意用眼衛(wèi)生。眼睛與文稿、眼睛與屏幕的距離應(yīng)保持在50厘米以上，最好采用光下視20度的視角。工作時，應(yīng)在面部及雙手涂抹防輻射的護(hù)膚油。

　　3、孕婦每周接觸電腦時間不超過20小時。要防止長時間坐位引起盆腔血液滯留不暢，做到張馳有度；要注意電腦與座椅坐姿的高低配合，讓胎兒健康發(fā)育。

　 　4、長期從事電腦操作者，應(yīng)多吃一些新鮮的蔬菜和水果。同時增加維生素A、B1、C、E的攝入。為預(yù)防角膜干燥、眼干澀、視力下降、甚至出現(xiàn)夜盲癥等， 電腦操作者應(yīng)多吃些富含維生素A的食物，如豆制口、魚、牛奶、核桃、青菜、大白菜，西紅柿、空心菜及新鮮水果等。維生素C可以有效地抑制細(xì)胞氧化。維生素 E主要作用是：降低膽固醇，清除身體內(nèi)垃圾，預(yù)防白內(nèi)障。核桃和花生中含有豐富的維生素E。維生素B1可以加強神經(jīng)細(xì)胞的營養(yǎng)，緩解神經(jīng)的緊張狀態(tài)。

　　5、每天泡點綠茶。茶葉中的脂多糖，可改善肌體造血工能。人體注入脂多糖后，在短時間內(nèi)即可增強機(jī)體非特異性免疫力。茶葉還能防輻射損害。

　　6、為了避免熒光屏反光或不清晰，電腦不應(yīng)放置在窗戶的對面或背面；環(huán)境照明要柔和，如果操作者身后有窗戶應(yīng)拉上窗簾，避免亮光直接照射到屏幕上反向出明亮的影像造成眼部的疲勞。

　　7、電腦房間要經(jīng)常通風(fēng)，在室內(nèi)安裝換氣扇或空調(diào)，減輕溴比二苯呋喃對身體的影響。計算機(jī)附近的灰塵密度要比機(jī)房其它空間高出上百倍，它們長時間附著于人的皮膚上，可導(dǎo)致各類皮膚病。電腦房間要保持清潔衛(wèi)生，電腦要定期擦洗。

　　8、一般人每分鐘眨眼少于5次會使眼睛干燥。一個人在電腦工作時眨睛次數(shù)只及平時的三分之一，因而減少了眼內(nèi)潤滑劑和酶的分泌。應(yīng)該多眨眼，每隔一小時至少讓眼睛休息一次。

???

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.

Output
1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

Solution

???

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.

Input?

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.

Output?

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.

Sample Input?

1
14
4
0

Sample Output?

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

Solution

#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ù)
????}
????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

				
日前在書上看到一段使用多項式逼近計算平方根的代碼，至今都沒搞明白作者是怎樣推
算出那個公式的。但在嘗試解決問題的過程中，學(xué)到了不少東西，于是便有了這篇心
得，寫出來和大家共享。其中有錯漏的地方，還請大家多多指教。

的確，正如許多人所說的那樣，現(xiàn)在有有FPU，有3DNow，有SIMD，討論軟件算法好像不
合時宜。關(guān)于sqrt的話題其實早在2003年便已在?GameDev.net上得到了廣泛的討論（可
見我實在非常火星了，當(dāng)然不排除還有其他尚在冥王星的人，嘿嘿）。而嘗試探究該話
題則完全是出于本人的興趣和好奇心（換句話說就是無知）。

我只是個beginner，所以這種大是大非的問題我也說不清楚（在GameDev.net上也有很多
類似的爭論）。但無論如何，Carmack在DOOM3中還是使用了軟件算法，而多知道一點數(shù)
學(xué)知識對3D編程來說也只有好處沒壞處。3D圖形編程其實就是數(shù)學(xué)，數(shù)學(xué)，還是數(shù)學(xué)。

文章原本是用HTML編排的，所以只截取了部分有比較有趣的東西放在這里。原文在我的
個人主頁上，同時也提供了2篇論文的下載：http:
//greatsorcerer.go2.icpcn.com/info/fastsqrt.html

=========================================================

在3D圖形編程中，經(jīng)常要求平方根或平方根的倒數(shù)，例如：求向量的長度或?qū)⑾蛄繗w一
化。C數(shù)學(xué)函數(shù)庫中的sqrt具有理想的精度，但對于3D游戲程式來說速度太慢。我們希望
能夠在保證足夠的精度的同時，進(jìn)一步提高速度。

Carmack在QUAKE3中使用了下面的算法，它第一次在公眾場合出現(xiàn)的時候，幾乎震住了所
有的人。據(jù)說該算法其實并不是Carmack發(fā)明的，它真正的作者是Nvidia的Gary?Tarolli
（未經(jīng)證實）。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
//?計算參數(shù)x的平方根的倒數(shù)
//
float?InvSqrt?(float?x)
{
float?xhalf?=?0.5f*x;
int?i?=?*(int*)&x;
i?=?0x5f3759df?-?(i?>>?1);?//?計算第一個近似根
x?=?*(float*)&i;
x?=?x*(1.5f?-?xhalf*x*x);?//?牛頓迭代法
return?x;
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
該算法的本質(zhì)其實就是牛頓迭代法（Newton-Raphson?Method，簡稱NR），而NR的基礎(chǔ)則
是泰勒級數(shù)（Taylor?Series）。NR是一種求方程的近似根的方法。首先要估計一個與方
程的根比較靠近的數(shù)值，然后根據(jù)公式推算下一個更加近似的數(shù)值，不斷重復(fù)直到可以
獲得滿意的精度。其公式如下：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
函數(shù)：y=f(x)
其一階導(dǎo)數(shù)為：y'=f'(x)
則方程：f(x)=0?的第n+1個近似根為
x[n+1]?=?x[n]?-?f(x[n])?/?f'(x[n])
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
NR最關(guān)鍵的地方在于估計第一個近似根。如果該近似根與真根足夠靠近的話，那么只需
要少數(shù)幾次迭代，就可以得到滿意的解。

現(xiàn)在回過頭來看看如何利用牛頓法來解決我們的問題。求平方根的倒數(shù)，實際就是求方
程1/(x^2)-a=0的解。將該方程按牛頓迭代法的公式展開為：
x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])
將1/2放到括號里面，就得到了上面那個函數(shù)的倒數(shù)第二行。

接著，我們要設(shè)法估計第一個近似根。這也是上面的函數(shù)最神奇的地方。它通過某種方
法算出了一個與真根非常接近的近似根，因此它只需要使用一次迭代過程就獲得了較滿
意的解。它是怎樣做到的呢？所有的奧妙就在于這一行：
i?=?0x5f3759df?-?(i?>>?1);?//?計算第一個近似根

超級莫名其妙的語句，不是嗎？但仔細(xì)想一下的話，還是可以理解的。我們知道，IEEE
標(biāo)準(zhǔn)下，float類型的數(shù)據(jù)在32位系統(tǒng)上是這樣表示的（大體來說就是這樣，但省略了很
多細(xì)節(jié)，有興趣可以GOOGLE）：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
bits：31?30?...?0
31：符號位
30-23：共8位，保存指數(shù)（E）
22-0：共23位，保存尾數(shù)（M）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
所以，32位的浮點數(shù)用十進(jìn)制實數(shù)表示就是：M*2^E。開根然后倒數(shù)就是：M^(-1/2)*2^
(-E/2)。現(xiàn)在就十分清晰了。語句i>?>1其工作就是將指數(shù)除以2，實現(xiàn)2^(E/2)的部分。
而前面用一個常數(shù)減去它，目的就是得到M^(1/2)同時反轉(zhuǎn)所有指數(shù)的符號。

至于那個0x5f3759df，呃，我只能說，的確是一個超級的Magic?Number。

那個Magic?Number是可以推導(dǎo)出來的，但我并不打算在這里討論，因為實在太繁瑣了。
簡單來說，其原理如下：因為IEEE的浮點數(shù)中，尾數(shù)M省略了最前面的1，所以實際的尾
數(shù)是1+M。如果你在大學(xué)上數(shù)學(xué)課沒有打瞌睡的話，那么當(dāng)你看到(1+M)^(-1/2)這樣的形
式時，應(yīng)該會馬上聯(lián)想的到它的泰勒級數(shù)展開，而該展開式的第一項就是常數(shù)。下面給
出簡單的推導(dǎo)過程：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
對于實數(shù)R>0，假設(shè)其在IEEE的浮點表示中，
指數(shù)為E，尾數(shù)為M，則：

R^(-1/2)
=?(1+M)^(-1/2)?*?2^(-E/2)

將(1+M)^(-1/2)按泰勒級數(shù)展開，取第一項，得：

原式
=?(1-M/2)?*?2^(-E/2)
=?2^(-E/2)?-?(M/2)?*?2^(-E/2)

如果不考慮指數(shù)的符號的話，
(M/2)*2^(E/2)正是(R>>1)，
而在IEEE表示中，指數(shù)的符號只需簡單地加上一個偏移即可，
而式子的前半部分剛好是個常數(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)
求出令到相對誤差最小的C值就可以了
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
上面的推導(dǎo)過程只是我個人的理解，并未得到證實。而Chris?Lomont則在他的論文中詳
細(xì)討論了最后那個方程的解法，并嘗試在實際的機(jī)器上尋找最佳的常數(shù)C。有興趣的朋友
可以在文末找到他的論文的鏈接。

所以，所謂的Magic?Number，并不是從N元宇宙的某個星系由于時空扭曲而掉到地球上
的，而是幾百年前就有的數(shù)學(xué)理論。只要熟悉NR和泰勒級數(shù)，你我同樣有能力作出類似
的優(yōu)化。

在GameDev.net?上有人做過測試，該函數(shù)的相對誤差約為0.177585%，速度比C標(biāo)準(zhǔn)庫的
sqrt提高超過20%。如果增加一次迭代過程，相對誤差可以降低到e-?004?的級數(shù)，但速
度也會降到和sqrt差不多。據(jù)說在DOOM3中，Carmack通過查找表進(jìn)一步優(yōu)化了該算法，
精度近乎完美，而且速度也比原版提高了一截（正在努力弄源碼，誰有發(fā)我一份）。

值得注意的是，在Chris?Lomont的演算中，理論上最優(yōu)秀的常數(shù)（精度最高）是
0x5f37642f，并且在實際測試中，如果只使用一次迭代的話，其效果也是最好的。但奇
怪的是，經(jīng)過兩次NR后，在該常數(shù)下解的精度將降低得非常厲害（天知道是怎么回
事！）。經(jīng)過實際的測試，Chris?Lomont認(rèn)為，最優(yōu)秀的常數(shù)是0x5f375a86。如果換成
64位的double版本的話，算法還是一樣的，而最優(yōu)常數(shù)則為?0x5fe6ec85e7de30da（又一
個令人冒汗的Magic?Number?-?-b）。

這個算法依賴于浮點數(shù)的內(nèi)部表示和字節(jié)順序，所以是不具移植性的。如果放到Mac上跑
就會掛掉。如果想具備可移植性，還是乖乖用sqrt好了。但算法思想是通用的。大家可
以嘗試推算一下相應(yīng)的平方根算法。

下面給出Carmack在QUAKE3中使用的平方根算法。Carmack已經(jīng)將QUAKE3的所有源代碼捐
給開源了，所以大家可以放心使用，不用擔(dān)心會受到律師信。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
//?Carmack在QUAKE3中使用的計算平方根的函數(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));
}

     摘要: 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.

Input and Output

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.

Sample Input

5
7
11

Sample Output

The Fibonacci number for 5 is 5
The Fibonacci number for 7 is 13
The Fibonacci number for 11 is 89

Solution

#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;

}

Background

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.

The Problem

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

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.

The Output

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).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

Solution ?

#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;

}