存档

‘趣味问题’ 分类的存档

如何用最有创造力的方式输出42

2014年3月6日 1 条评论 323 人阅读    

酷壳似乎好长时间没有像《编程真难啊》或是《老手是这样教新手编程的》或是像《如何写出无法维护的代码》这样“严肃正经”的文章了,所以,赶在大家还没有向我扔臭鸡蛋前奉献一篇。这篇文章来自CodeGolf.StackExchange上的《Most creative way to display 42》—— 请以最有创造力的方式输出42。于是出现了下面的这些答案(注:精彩的总是留在最后面)

人生和宇宙终级问题的答案:42

这里,需要介绍一下为什么要输出42。这时因为42是我们人生,世界乃至整个宇宙的终级答案。这要从《银河系漫游指南》(英文名:The Hitchhiker’s Guide to the Galaxy)说起。这本书是著名英国科幻小说作家Douglas  Adams所著5本银河系漫游指南系列科幻喜剧系列小说中的第一本,改编自他本人为英国广播公司第四电台(BBC Radio 4)所写的广播剧剧本。该书1979年10月12日首次由麦克米伦出版公司(Pan Books)出版,次周成为英国图书销量榜冠军,前3个月内销售超过25万本。截至2005年,这本小说已被翻译成超过30种语言在全世界发行,并且被改编为电视剧、电影、舞台剧等多种艺术形式的作品。

这本小说中小说中充满尖锐的讽刺和隐喻,被西方科幻爱好者奉为“科幻圣经”。其中有两个关键词,一个是Don’t Panic,一个是42影响力很大,而其中关于42的故事简介是这样的:

百万年前,老鼠其实是一种超智慧生物,它们建造了一部超级电脑深思Deep Thought,它们问超级电脑,生命、宇宙以及任何事情的终极答案(Answer to Life, the Universe, and Everything)什么,经过了750万年的计算,深思告诉老鼠的后人答案是42,深思解释它只能计算出答案是什么,但答案的原因必须由另一部更高智能的电脑才能解释,而该部电脑就是地球。经过了800万年,就在结果要出来的五分钟前,地球却因为挡在预定兴建的星际间高速公路的路线,被Vogons给毁灭,电脑没有给出最后的结果。

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (1 人打了分,平均分: 5.00 )
Loading ... Loading ...

一个“蝇量级” C 语言协程库

2014年1月28日 29 条评论 17,525 人阅读    

(感谢网友 @我的上铺叫路遥 投稿)

协程(coroutine)顾名思义就是“协作的例程”(co-operative routines)。跟具有操作系统概念的线程不一样,协程是在用户空间利用程序语言的语法语义就能实现逻辑上类似多任务的编程技巧。实际上协程的概念比线程还要早,按照 Knuth 的说法“子例程是协程的特例”,一个子例程就是一次子函数调用,那么实际上协程就是类函数一样的程序组件,你可以在一个线程里面轻松创建数十万个协程,就像数十万次函数调用一样。只不过子例程只有一个调用入口起始点,返回之后就结束了,而协程入口既可以是起始点,又可以从上一个返回点继续执行,也就是说协程之间可以通过 yield 方式转移执行权,对称(symmetric)、平级地调用对方,而不是像例程那样上下级调用关系。当然 Knuth 的“特例”指的是协程也可以模拟例程那样实现上下级调用关系,这就叫非对称协程(asymmetric coroutines)。

基于事件驱动模型

我们举一个例子来看看一种对称协程调用场景,大家最熟悉的“生产者-消费者”事件驱动模型,一个协程负责生产产品并将它们加入队列,另一个负责从队列中取出产品并使用它。为了提高效率,你想一次增加或删除多个产品。伪代码可以是这样的:

# producer coroutine
loop
while queue is not full
  create some new items
  add the items to queue
yield to consumer

# consumer coroutine
loop
while queue is not empty
  remove some items from queue
  use the items
yield to producer

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (20 人打了分,平均分: 5.00 )
Loading ... Loading ...

伙伴分配器的一个极简实现

2013年10月9日 41 条评论 14,527 人阅读    

(感谢网友 @我的上铺叫路遥 投稿)

提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现,而仅仅是将该算法抽象提取出来,同时给出一份及其简洁的源码实现,以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”,即将内存按2的幂进行划分,相当于分离出若干个块大小一致的空闲链表,搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并(O(logN)时间复杂度)以及低外部碎片(最佳适配best-fit);其缺点是内部碎片,因为按2的幂划分块,如果碰上66单位大小,那么必须划分128单位大小的块。但若需求本身就按2的幂分配,比如可以先分配若干个内存池,在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述,大体如是:

分配内存:

1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂,比如需要27,实际分配32)

1.如果找到了,分配给应用程序。
2.如果没找到,分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度,分配这个大小。
3.回溯到步骤1(寻找合适大小的块)
4.重复该步骤直到一个合适的块

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 4.79 )
Loading ... Loading ...

一个fork的面试题

2012年8月1日 94 条评论 58,566 人阅读    

前两天有人问了个关于Unix的fork()系统调用的面试题,这个题正好是我大约十年前找工作时某公司问我的一个题,我觉得比较有趣,写篇文章与大家分享一下。这个题是这样的:

题目:请问下面的程序一共输出多少个“-”?

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main(void)
{
   int i;
   for(i=0; i<2; i++){
      fork();
      printf("-");
   }

   return 0;
}

如果你对fork()的机制比较熟悉的话,这个题并不难,输出应该是6个“-”,但是,实际上这个程序会很tricky地输出8个“-”。

要讲清这个题,我们首先需要知道fork()系统调用的特性,

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (22 人打了分,平均分: 4.86 )
Loading ... Loading ...

神奇的CSS形状

2012年3月24日 18 条评论 16,482 人阅读    

感谢 Neo 投递本文 – 微博帐号@_锟_

在StackOverflow上有这么一个问题,有位同学在http://css-tricks.com/examples/ShapesOfCSS/  找到一些使用CSS做的形状,其中一位同学对下面的这个形状充满了疑问。

形状是:

代码是:

#triangle-up {
width: 0;
height: 0;
border-left: 50px solid transparent;
border-right: 50px solid transparent;
border-bottom: 100px solid red;
}

这位同学就提问啦,为啥这么这么几句就能画出一个三角形呢?
于是呢,有高人出现,这个高人图文并茂的解释了这个三角的成因

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 4.07 )
Loading ... Loading ...

软件真的好难做啊

2011年6月10日 70 条评论 20,846 人阅读    

还记得以前本站的那一篇“编程好难啊”吗,那是一篇众程序员调侃程序新手的文章,有恶搞的成分在里面。今天要和大家说的这个事没有一些恶搞和调侃的意思,是比较严肃的话题,你一定可以从中收获一些东西。这个话题来自StackOverflow上的一个问题——Cycle in Family Tree Software,这个程序员问了下面这个问题:

我是一个写家族族谱软件的程序员(我用的是C++和Qt),这个软件基本上没有什么问题,直到有一天有个用户报告了一个bug。这个问题是这样的——我这个用户和他女儿生了两个孩子

于是,我程序员的一些断言和硬性条件导致程序报错,因为我的程序在处理这个关系的时候,其发现X即是Y的爸爸,又是Y的爷爷,所以只能报错。

请问,在不需要移除我的断言和数据验证的情况下,我怎么才能解决这个问题

看到这里,请重点阅读一下下面的两点:

  • 如果你看到这里开始兴奋了,请你为你阴暗的心理去面壁反省10分钟,因为这是一个很技术的问题。
  • 如果你开始陷入了深深的思考如何解决这个问题,那么你绝对是一个合格的程序员,因为你已陷入技术已经很深了,有点呆了。

我在前面说过,“这个是一个严肃的话题,你可以从中收获一些东西”,当然,我并不希望你来收获乱伦的知识和心得,酷壳是一个技术博客,应该是收获技术方面的东西。

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 4.92 )
Loading ... Loading ...

面试题:火车运煤问题

2011年4月11日 248 条评论 69,974 人阅读    

这个可能是一个比较经典的智力题了,和以前的那个《赛马问题》很相似,其题目如下:

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。

如果你一开始就觉得不太可能的话,这是很正常的。不过我不知道你还会不会继续思考下去,如果你不想思考下去了,那么我很为你担忧,因为你可能并不是一个不善于思考的人,而是一个畏难的人,还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。

我一开始也觉得不可能,后来想了一想,想到一个解法可以最多运送500吨煤到市场,方法如下:(希望你先自己想一想再查看这个答案
阅读全文…

好烂啊有点差凑合看看还不错很精彩 (43 人打了分,平均分: 4.84 )
Loading ... Loading ...

又一个有趣的面试题

2011年4月2日 53 条评论 27,704 人阅读    

大家还记得前些天的那个火柴棍式的面试题吗?很有趣吧。下面是我今天在StackExchange上看到的一个有趣的面试题。大家不妨一起来思考一下。问题如下——

有两个相同功能代码如下,请在在A,B,C是什么的情况下,请给出三个原因case 1比case 2快,还有三个原因case 2会比case 1要执行的快。(不考虑编译器优化)

for (i=0; i<N; ++i){
    A;
    B;
    C;
}
for (i=0; i<N; ++i){
    A;
}
for (i=0; i<N; ++i){
    B;
}
for (i=0; i<N; ++i){
    C;
}

我的第一个反应是——

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (11 人打了分,平均分: 5.00 )
Loading ... Loading ...

“火柴棍式”程序员面试题

2011年3月21日 2,695 条评论 47,385 人阅读    

有时候,有些面试题是很是无厘头,这不,又有一个,还记得小时候玩的的“火柴棍游戏”吗,就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩,看看下面这个火柴棍式的程序面试题吧。

下面是一个C程序,其想要输出20个减号,不过,粗心的程序员把代码写错了,你需要把下面的代码修改正确,不过,你只能增加或是修改其中的一个字符,请你给出三种答案。

int n = 20;

for(int i = 0; i < n; i--){
    printf("-");
}

不要以为这题不是很难,我相信你并不那么容易能找到3种方法。我觉得,如果你能在10分钟内找出这三种方法,说明你真的很聪明,而且反应很快。当然,15分钟内也不赖。不过,你要是30分钟内找不到三种方法,当然,不说明你笨了,最多就是你的反应还不够快。嘿嘿。就当是玩玩吧。

下面是我的答案:

//第一种解法:在for循环中给n加一个负号
for(int i = 0; i < -n; i--)

//第二种解法:把 n 初始化成 -20
int n = -20;

//第三种解法:把for循环中的 i 初始化成40
for(int i = 40; i < n; i--)

不过,我要告诉你,以上这些答案都不对(我就知道你会偷看答案的),不过,顺着这些思路走很接近了。呵呵。

下面是正确答案——

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (35 人打了分,平均分: 4.83 )
Loading ... Loading ...

打印质数的各种算法

2011年2月28日 29 条评论 11,926 人阅读    

打印质数的算法应该是学习计算机编程的一个经典的问题,在这里想给大家展示一些方法,相信这些方法会对你的编程有一定的启发作用。请你注意几点,

  • 实际应用和教学应用有很大的差别。
  • 最后的那个使用编译时而不是运行时的方法大家可以重点看看。

教科书的示例

首先,先给一个教科书的示例。下面这个示例应该是教科书(至少是我上大学时的教科学)中算法复杂度最好的例子了。其想法很简单,先写一个判断是否是质数的函数isPrime(),然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心,其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n)),看上去不错,但其实很不经济。

#include <iostream>
using namespace std;

bool isPrime(int nr)
{
    for (int d = 2; (d * d) < (nr + 1); ++d){
        if (!(nr % d)){
            return false;
        }
     }
    return true;
}

int main (int argc, char * const argv[])
{
    for (int i = 0; i < 50; ++i){
        if (isPrime(i)){
            cout << i << endl;
        }
    }
}

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (7 人打了分,平均分: 4.71 )
Loading ... Loading ...