《挑战程序设计竞赛》读书笔记(四)格点问题的证明

《挑战程序设计竞赛》读书笔记(四)格点问题的证明

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题,该解答给出了结果,但中间过程省略了不少内容。本文补充了相关的证明和解释。
问题描述如下:
格点是指平面坐标系中,横纵坐标都是整数的点。给定平面上两个格点,P1(x1,y1),P2(x2,y2),则线段P1P2上除了P1和P2外,有几个格点?事实上,该问题答案为|x2-x1|和|y2-y1|的最大公约数减1,并给出了一个图示。本文对该结论给出了证明。

写跨平台C语言代码的十个规则

写跨平台C语言代码的十个规则

翻译了一篇关于写跨平台C语言代码的文章,介绍了10个相关规则。Rule #1: 同时开发 – 不要先开发后移植。不要把迁移工作外包。Rule #3: 使用标准C类型,不要使用特定于平台的类型。Rule #4: 只使用内置的 #ifdef 编译标志,不要自己发明轮子。 Rule #5: 开发一个简单的可重用的跨平台的基础库,来隐藏每个平台的代码。Rule 6#: 在所有的API中都使用Unicode(特别是UTF-8)。Rule #7: 不要使用第三方应用程序框架或者运行时环境来是你的代码跨平台。Rule #8: 原生代码本来就总是可以所有平台上编译->不是某个脚本让它们从不能编译变得能够编译了。 Rule #9:所有的程序都能在所有的平台编译。Rule #10:开除那些懒惰、不称职、态度差、不遵循这些规则的程序员。

几道面试趣题( 打印重复数字 编码扑克牌 煎饼堆排序 随机选取数字 统计1的个数 )

几道面试趣题( 打印重复数字  编码扑克牌  煎饼堆排序  随机选取数字  统计1的个数 )

逛Quora的时候,看到一个有趣的问题。”What are the best programming interview questions you've ever asked or been asked?” (在编程面试中,你问过或者被问过的最好的问题是什么)里面有几道题目很有意思,在这里分享给大家。
第一道题:有一个长度为N+1的数组,里面的元素都是1~N的整数,但有些数字可能重复多次。例如1,1,3 ,3或者 1,3,2,2。现在要求打印出重复的数字(有多个数字重复时,可打印任意一个)。
第二道题目:去掉大小王的52张扑克牌,你和你的朋友事先约定一种策略,使得:我任意给你5张扑克牌,你选择一张留下,剩余的4张给你的朋友,你的朋友能够根据事先约定的策略,知道你留下的牌是什么。
从连续不断的数字流中随机选取一个数字(数字流只能过一遍),要求保证任意时刻,已经过去的数字流中任意一个数字被选中的概率相等。
给定整数N,计算从1到N的数字的二进制表示中所有1的个数。