技术，瞎侃，健康，休闲……

第一个是递归版本的：（没什么意思）

 

 

 

第二个是递归版本的：（没有用栈，因此还比较精妙）

对不起，由于一时疏忽，把两个版本的程序贴成同一个了，十分抱歉，谢谢您的提醒，现更正如下：

 

在水木上见到一个贴子，关于虚函数的访问权限问题：

其实这是一个关于访问权限决定时间的问题，由于访问权限是编译时间决定的，而不是运行时决定的。
B *bp = new D;  // 此时bp所指向的类型是B而不是D，而B的f3()是公有的，所以可以访问。
D *dp = new D; // 此时dp所指向的类型是D，而D的f3()是私有的，所以不能访问。

    zz:程序员每天该做的事 
1、总结自己一天任务的完成情况 
最好的方式是写工作日志，把自己今天完成了什么事情，遇见了什么问题都记录下来，日后翻看好处多多 

2、考虑自己明天应该做的主要工作 
把明天要做的事情列出来，并按照优先级排列，第二天应该把自己效率最高的时间分配给最重要的工作 

3、考虑自己一天工作中失误的地方，并想出避免下一次再犯的方法 
出错不要紧，最重要的是不要重复犯相同的错误，那是愚蠢 

4、考虑自己一天工作完成的质量和效率能否还能提高 
一天只提高1%，365天你的效率就能提高多少倍你知道吗？ (1+0.01)^365 = 37 倍 

5、看一个有用的新闻网站或读一张有用的报纸，了解业界动态 
闭门造车是不行的，了解一下别人都在做什么，对自己能带来很多启示 

6、记住一位同事的名字及其特点 
你认识公司的所有同事吗？你了解他们吗？ 

7、清理自己的代码 
今天完成的代码，把中间的调试信息，测试代码清理掉，按照编码风格整理好，注释都写好了吗？ 

8、清理自己的桌面 
当日事当日毕，保持清洁干劲的桌面才能让你工作时不分心，程序员特别要把电脑的桌面清理干净 

程序员每周该做的事 
1、向你的老板汇报一次工作 
让你的老板知道你在做什么，这很重要。可以口头、书面、邮件，看你老板的工作方式而定 

2、进行一次自我总结（非正式） 
这周之内自己表现得怎么样？该加分还是扣分？ 

3、制定下周计划 
把下周要做的事情列出来，一样要分清楚优先级 

4、整理自己的文件夹、书柜和电脑文件 
把桌面以外的地方也要清理干净，电脑的文件夹，收到的邮件，把过时的垃圾全部清理掉 

5、与一个非公司的朋友沟通 
它山之石，可以攻玉 

6、看一本杂志 
找一本适合自己的专业杂志 

7、纠正自己或同事一个细节上的不正确做法 
《细节决定成败》看过了吗？没看过强烈建议先看看 

程序员每月该做的事 
1、至少和一个同事一起吃饭或喝茶 
不光了解自己工作伙伴的工作，还要了解他们的生活 

2、自我考核一次 
相对正式地考核自己一下，你对得起这个月的工资吗？ 

3、对你的同事考核一次 
你的同事表现怎么样？哪些人值得学习，哪些人需要帮助？ 

4、制定下月的计划，确定下月的工作重点 

5、总结自己工作质量改进状况 
自己的质量提高了多少？ 

6、有针对性地对一项工作指标做深入地分析并得出改进的方案 
可以是对自己的，也可以是对公司的，一定要深入地分析后拿出自己的观点来。要想在老板面前说得上话，做的成事，工作上功夫要做足。 

7、与老板沟通一次 
最好是面对面地沟通，好好表现一下自己，虚心听取老板的意见，更重要的是要了解老板当前关心的重点 

程序员每年该做的事 
1、年终总结 
每个公司都会做的事情，但你真正认真地总结过自己吗？ 

2、兑现给自己、给家人的承诺 
给老婆、儿子的新年礼物买了没有？给自己的呢？ 

3、下年度工作规划 
好好想想自己明年的发展目标，争取升职/加薪、跳槽还是自己出来干？ 

4、掌握一项新技术 
至少是一项，作为程序员一年要是一项新技术都学不到手，那就一定会被淘汰。 
掌握可不是看本书就行的，要真正懂得应用，最好你能够写一篇教程发表到你的blog 

5、推出一种新产品 
可以是一个真正的产品，也可以只是一个类库，只要是你创造的东西就行，让别人使用它，也为世界作点贡献。当然如果真的很有价值，收点注册费也是应该的 

6、与父母团聚一次 
常回家看看，常回家看看

   

    1、注意劳逸结合，防止肌腱劳损。长时间操作电脑会导致手指关节、手腕、手臂肌肉、双肩、颈部、背部等部位出现酸胀疼痛，因此，操作者在工作一小时后应休息10分钟，或者做做工间操。

　　2、要注意用眼卫生。眼睛与文稿、眼睛与屏幕的距离应保持在50厘米以上，最好采用光下视20度的视角。工作时，应在面部及双手涂抹防辐射的护肤油。

　　3、孕妇每周接触电脑时间不超过20小时。要防止长时间坐位引起盆腔血液滞留不畅，做到张驰有度；要注意电脑与座椅坐姿的高低配合，让胎儿健康发育。

　 　4、长期从事电脑操作者，应多吃一些新鲜的蔬菜和水果。同时增加维生素A、B1、C、E的摄入。为预防角膜干燥、眼干涩、视力下降、甚至出现夜盲症等， 电脑操作者应多吃些富含维生素A的食物，如豆制口、鱼、牛奶、核桃、青菜、大白菜，西红柿、空心菜及新鲜水果等。维生素C可以有效地抑制细胞氧化。维生素 E主要作用是：降低胆固醇，清除身体内垃圾，预防白内障。核桃和花生中含有丰富的维生素E。维生素B1可以加强神经细胞的营养，缓解神经的紧张状态。

　　5、每天泡点绿茶。茶叶中的脂多糖，可改善肌体造血工能。人体注入脂多糖后，在短时间内即可增强机体非特异性免疫力。茶叶还能防辐射损害。

　　6、为了避免荧光屏反光或不清晰，电脑不应放置在窗户的对面或背面；环境照明要柔和，如果操作者身后有窗户应拉上窗帘，避免亮光直接照射到屏幕上反向出明亮的影像造成眼部的疲劳。

　　7、电脑房间要经常通风，在室内安装换气扇或空调，减轻溴比二苯呋喃对身体的影响。计算机附近的灰尘密度要比机房其它空间高出上百倍，它们长时间附着于人的皮肤上，可导致各类皮肤病。电脑房间要保持清洁卫生，电脑要定期擦洗。

　　8、一般人每分钟眨眼少于5次会使眼睛干燥。一个人在电脑工作时眨睛次数只及平时的三分之一，因而减少了眼内润滑剂和酶的分泌。应该多眨眼，每隔一小时至少让眼睛休息一次。

   

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;    // 增加后的总面数,numSides为实际的总面数
    }
    else
        numSidesNew = numSides;
    pages = numSidesNew / 4;    // 总纸张数
    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;    // 表明应为blank
        }
        sheets[i].front.right = 2*i+1;
        if(sheets[i].front.right > numSides){
            sheets[i].front.right = 0;    // 表明应为blank
        }
        sheets[i].back.left = 2*(i+1);
        if(sheets[i].back.left > numSides){
            sheets[i].back.left = 0;    // 表明应为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

				
日前在书上看到一段使用多项式逼近计算平方根的代码，至今都没搞明白作者是怎样推
算出那个公式的。但在尝试解决问题的过程中，学到了不少东西，于是便有了这篇心
得，写出来和大家共享。其中有错漏的地方，还请大家多多指教。

的确，正如许多人所说的那样，现在有有FPU，有3DNow，有SIMD，讨论软件算法好像不
合时宜。关于sqrt的话题其实早在2003年便已在 GameDev.net上得到了广泛的讨论（可
见我实在非常火星了，当然不排除还有其他尚在冥王星的人，嘿嘿）。而尝试探究该话
题则完全是出于本人的兴趣和好奇心（换句话说就是无知）。

我只是个beginner，所以这种大是大非的问题我也说不清楚（在GameDev.net上也有很多
类似的争论）。但无论如何，Carmack在DOOM3中还是使用了软件算法，而多知道一点数
学知识对3D编程来说也只有好处没坏处。3D图形编程其实就是数学，数学，还是数学。

文章原本是用HTML编排的，所以只截取了部分有比较有趣的东西放在这里。原文在我的
个人主页上，同时也提供了2篇论文的下载：http:
//greatsorcerer.go2.icpcn.com/info/fastsqrt.html

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

在3D图形编程中，经常要求平方根或平方根的倒数，例如：求向量的长度或将向量归一
化。C数学函数库中的sqrt具有理想的精度，但对于3D游戏程式来说速度太慢。我们希望
能够在保证足够的精度的同时，进一步提高速度。

Carmack在QUAKE3中使用了下面的算法，它第一次在公众场合出现的时候，几乎震住了所
有的人。据说该算法其实并不是Carmack发明的，它真正的作者是Nvidia的Gary Tarolli
（未经证实）。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
// 计算参数x的平方根的倒数
//
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;
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
该算法的本质其实就是牛顿迭代法（Newton-Raphson Method，简称NR），而NR的基础则
是泰勒级数（Taylor Series）。NR是一种求方程的近似根的方法。首先要估计一个与方
程的根比较靠近的数值，然后根据公式推算下一个更加近似的数值，不断重复直到可以
获得满意的精度。其公式如下：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
函数：y=f(x)
其一阶导数为：y'=f'(x)
则方程：f(x)=0 的第n+1个近似根为
x[n+1] = x[n] - f(x[n]) / f'(x[n])
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
NR最关键的地方在于估计第一个近似根。如果该近似根与真根足够靠近的话，那么只需
要少数几次迭代，就可以得到满意的解。

现在回过头来看看如何利用牛顿法来解决我们的问题。求平方根的倒数，实际就是求方
程1/(x^2)-a=0的解。将该方程按牛顿迭代法的公式展开为：
x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])
将1/2放到括号里面，就得到了上面那个函数的倒数第二行。

接着，我们要设法估计第一个近似根。这也是上面的函数最神奇的地方。它通过某种方
法算出了一个与真根非常接近的近似根，因此它只需要使用一次迭代过程就获得了较满
意的解。它是怎样做到的呢？所有的奥妙就在于这一行：
i = 0x5f3759df - (i >> 1); // 计算第一个近似根

超级莫名其妙的语句，不是吗？但仔细想一下的话，还是可以理解的。我们知道，IEEE
标准下，float类型的数据在32位系统上是这样表示的（大体来说就是这样，但省略了很
多细节，有兴趣可以GOOGLE）：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
bits：31 30 ... 0
31：符号位
30-23：共8位，保存指数（E）
22-0：共23位，保存尾数（M）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
所以，32位的浮点数用十进制实数表示就是：M*2^E。开根然后倒数就是：M^(-1/2)*2^
(-E/2)。现在就十分清晰了。语句i> >1其工作就是将指数除以2，实现2^(E/2)的部分。
而前面用一个常数减去它，目的就是得到M^(1/2)同时反转所有指数的符号。

至于那个0x5f3759df，呃，我只能说，的确是一个超级的Magic Number。

那个Magic Number是可以推导出来的，但我并不打算在这里讨论，因为实在太繁琐了。
简单来说，其原理如下：因为IEEE的浮点数中，尾数M省略了最前面的1，所以实际的尾
数是1+M。如果你在大学上数学课没有打瞌睡的话，那么当你看到(1+M)^(-1/2)这样的形
式时，应该会马上联想的到它的泰勒级数展开，而该展开式的第一项就是常数。下面给
出简单的推导过程：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
对于实数R>0，假设其在IEEE的浮点表示中，
指数为E，尾数为M，则：

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

将(1+M)^(-1/2)按泰勒级数展开，取第一项，得：

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

如果不考虑指数的符号的话，
(M/2)*2^(E/2)正是(R>>1)，
而在IEEE表示中，指数的符号只需简单地加上一个偏移即可，
而式子的前半部分刚好是个常数，所以原式可以转化为：

原式 = C - (M/2)*2^(E/2) = C - (R>>1)，其中C为常数

所以只需要解方程：
R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)
= C - (R>>1)
求出令到相对误差最小的C值就可以了
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
上面的推导过程只是我个人的理解，并未得到证实。而Chris Lomont则在他的论文中详
细讨论了最后那个方程的解法，并尝试在实际的机器上寻找最佳的常数C。有兴趣的朋友
可以在文末找到他的论文的链接。

所以，所谓的Magic Number，并不是从N元宇宙的某个星系由于时空扭曲而掉到地球上
的，而是几百年前就有的数学理论。只要熟悉NR和泰勒级数，你我同样有能力作出类似
的优化。

在GameDev.net 上有人做过测试，该函数的相对误差约为0.177585%，速度比C标准库的
sqrt提高超过20%。如果增加一次迭代过程，相对误差可以降低到e- 004 的级数，但速
度也会降到和sqrt差不多。据说在DOOM3中，Carmack通过查找表进一步优化了该算法，
精度近乎完美，而且速度也比原版提高了一截（正在努力弄源码，谁有发我一份）。

值得注意的是，在Chris Lomont的演算中，理论上最优秀的常数（精度最高）是
0x5f37642f，并且在实际测试中，如果只使用一次迭代的话，其效果也是最好的。但奇
怪的是，经过两次NR后，在该常数下解的精度将降低得非常厉害（天知道是怎么回
事！）。经过实际的测试，Chris Lomont认为，最优秀的常数是0x5f375a86。如果换成
64位的double版本的话，算法还是一样的，而最优常数则为 0x5fe6ec85e7de30da（又一
个令人冒汗的Magic Number - -b）。

这个算法依赖于浮点数的内部表示和字节顺序，所以是不具移植性的。如果放到Mac上跑
就会挂掉。如果想具备可移植性，还是乖乖用sqrt好了。但算法思想是通用的。大家可
以尝试推算一下相应的平方根算法。

下面给出Carmack在QUAKE3中使用的平方根算法。Carmack已经将QUAKE3的所有源代码捐
给开源了，所以大家可以放心使用，不用担心会受到律师信。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
// Carmack在QUAKE3中使用的计算平方根的函数
//
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;

}