标签归档:算法

谈谈创新与知识结构

(本文所有图片来源于网络)

ppap

“I have an apple, I have a pen… Ugh! Apple Pen!”

“I have a problem, I have an idea, (?), Innovation!”

创新到底是一个怎样的过程?

从发现一个问题,并想到用某种方法解决问题,到实际解决问题,中间实际上还隔着一层“窗户纸”。对于一个问题,能够想到某个想法的人很多,但这个想法通常不能直接简单地应用到问题上面;能够捅破这层“窗户纸”,让想法从不可用变成可用的人,其实是很少的。而所谓的创新,其实并不只是想到某个想法,更重要的是“捅破窗户纸”,让这个想法变得可用、成为现实。

继续阅读

简单均匀Open Hashing的Search操作平均时间复杂度证明

在HKU的COMP2119 Intro to DS&A课程中的一点收获,以前学习数据结构时没有这么注意理论细节,导致今天一开始没有搞明白,现在大概清楚了,在这里记录一下。写得比较啰嗦,主要是为了容易看懂。Wordpress自带的编辑器打公式实在是太蛋疼了,以后有空要好好整理一下。

继续阅读

排列(《算法竞赛入门经典》习题2-10)

本题(算法竞赛入门经典 第二章习题2-10)极水,我还写个解题报告,足以证明我有多弱菜了。

本题有多种做法,效率不一。下面介绍三种我使用的方法。
1、受本章开始的7744问题的启发,依次枚举abc,def,ghi,编写一个check()函数,用以判断这三个数是否把1~9的9个数字每个用了一遍,若是,则符合要求,输出。不幸的是,因为这样做不好判重(实际上也没有判重),用了5s左右才计算出所有四个解。舍弃之。
2、在网上搜索本题,发现真是有人把题目的最后一句(“提示:不必太动脑筋。”)理解得非常透彻,利用九重循环abcdefghi分别1~9,层层判重,最后一层判断是否合题目要求,是则输出。经我自己重新编写测试,出解大约需要0.85s。仔细阅读原程序后,发现有两个很好的优化:
(1)d可以直接从2a开始循环,g可以直接从3a开始循环,原因显而易见(a:b:c=1:2:3)。
(2)不必计算x=100a+10b+c,y=…,z=…然后判断xyz关系,直接用abcdefghi判断即可,这样可以节省大量时间。输出时用printf(“%d%d%d,%d%d%d,%d%d%d\n”,a,b,c,d,e,f,g,h,i);即可。
优化后,约0.15s出四解。
继续阅读

C语言随机数趣味小练习——猜数

今天下午信息课闲来无事,下载了code::blocks(刚知道的,一个很好用的IDE),编程序玩。想起自己C语言里的随机数还不会用,于是就在网上查资料查到了两句代码。一时兴起,编了这么一个猜数的程序。

先说随机数的代码(简易版)。

 

继续阅读