Archives for posts tagged ‘Programming’

数组的Shuffle操作

今天的题目: 实现Random Shuffle的功能,给你一个随机数发生器把一个数组里的元素乱序。 关于“随机乱序“这个概念,我自己的定义是1)新数列和就数列中元素排列的顺序不一样,是为乱序;2)乱序后不能以某种规律来恢复原序,是为随机。 我的思路: 随机从数组A中选一个数,将之作为输出数组的第一个元素,然后将这个元素从数组A中删除得到A’,再从 A’中随机选一个元素,将之作为输出数组的第二个元素。 如此循环下去,得到的输出数组就是一个随机大乱原有数组元素排序的新数组。 地里还有个思路: for(int i=0; i<n; i++) swap(x[n],x[rand()%(n)]); 每次都用数组最后一个数,和前面随机位置的数交换。 这个思路比我的思路要简洁,节省了存储空间。而且因该也满足以上我对题目的理解。然后从这个算法还能衍生别的算法,比如先随到一个m,然后将原数列分成A[0]-A[m]和A[m+1]-A[n-1]两个数列,然后将两个数列分别按照上面的方法打乱顺序。 如果还想跟随机一点,那么不要用数组最后一个位置的数与之前的数交换,而是用数组中随机的一个位置作为一个交换位置,总是让这个位置上的数随机的同它之前或者之后的某一个数交换。

简单的计算程序

今天的题目是: 如何写出一个简单的4则运算的程序。如输入 ” 1 -2*3 + 6/3″ ,输出 -3。只用支持正整数,不用考虑有括号的情况。 思路:因为不用考虑括号,所以乘和除的优先级最高。可以先把输入字符串用“+”和“-”分隔成一个数组,数组的结构是一个数字和符号间隔,把乘除法的项当作一个数字处理,如题目中的输入会被分成[“1″,”-“,”2*3″,”+”,”6/3″],然后再每三个数组项计算一次,把得到的结果加入到剩下的数组里,递归计算。如果计算过程中碰到还有乘除法的项,如”2*3″,则先把这个项算出来。 具体代码如下:

Bitwise和Shifting写乘法函数

写在前面—— 准备从这周开始,平常每两天一道题,周末争取一天一道题,练练招式。题目会源自一个叫做CareerCup的网站(需翻了个墙),上面有各种IT公司的面试题,基本集中在基础算法方面。这将成为我的博客中的一个系列——“做做题”。 今天的题目是: “Write a code which return square of any number, but you can not use Star or caret sign” 我的第一个思路就是把这个数加N遍就好了: 但是这个解显然只对整数有效,并且效率低下,我试了一下100000000,一分钟过去了还的不到结果,然后强制终止的时候,python崩溃了……

用互联网帮助你学习编程

用互联网除了可以帮助你谈恋爱,还能帮助你学习各种知识,在Academic Earth这个网站上聚合了众多美国知名大学的Open Course,Open Course就是把真实的美国大学课堂的录像放在互联网上给全世界的人免费观看,让无缘或者暂时还不能进入这些大学的人感受这些高等学府的课堂氛围。课程的范围很广,从Astronomy到Medicine都有。其实我去年就开始看斯坦福的一些开放课程,直到今年发现这个聚合网站,在加上iTunes在国外的速度较快、丰富的电子书和Google Calendar的短信提醒功能,我终于能有计划有进度的自学编程知识。 (Via)

关于咖啡豆的数学问题

在Guo Jing的Blog上看到这样一个数学问题 给定一个盛有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆额外的黑色豆子,重复以下过程,直至罐中仅剩一颗豆子为止。 从罐中随机选取两颗豆子,如果颜色相同,就将它们都扔掉并且放入一个额外的黑色豆子,如果颜色不同,就将白色的豆子放回罐中,而将黑色的豆子扔掉。 证明该过程会终止。最后留在罐中的豆子颜色与最初的罐中的白色豆子和黑色豆子的数量有什么数学关系。 (via) 用循环的算法写出代码后,他写到 也就是说,无论我们怎么拿豆子,白色的豆子的取出的过程都是,2个,0个,2个,0个。 也就是说,白色的豆子为偶数个的时候,留下的一定是黑色,而白色豆子为奇数的时候,留下的一定是白色! 道理是对的,但是证明过程似乎有点简略了。