2007年3月8日 星期四

CMClass: 微軟徵才試題 (完)

算錯篇: http://fourdollars.blogspot.com/2007/03/cmclass.html
算對篇: http://fourdollars.blogspot.com/2007/03/cmclass_08.html
這篇要來個總結... :P
原始的題目是
永源拿了兩個不同數字...
這兩個數字分別大於 1 ,也分別小於 50
永源只把這兩個數字的乘積告訴了亞譚 ...
永源再只把這兩個數字的和告訴了明歆 ...
永源問, 這兩個數字是什麼 ?

以下是亞譚和明歆的對話... (小強, 小毛, 小燕在旁坐陪)
亞譚: 我不知道這兩個數字是什麼!
明歆: 但我也還是不知道這兩個數字是什麼!
亞譚: 喔!那我知道那兩個數字是什麼了 !
明歆: 喔!那我也知道那兩個數字是什麼了 !
突然間 ....聰明的三位陪客同時也說: 我們也知道那兩個數字是什麼了 !
聰明的你, 告訴我....那兩個數字是什麼 ?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "set.h"

#define LOWER 2
#define UPPER 49

#define for_ij_do(A...) \
for (i = LOWER; i <= UPPER - 1; i++) \
for (j = i + 1; j <= UPPER; j++) \
do { A } while (0);

int main(int argc, char *argv[])
{
int i,j;

int m[UPPER * UPPER] = {0};
int a[UPPER + UPPER] = {0};

Set *setA = newSet();
Set *setB = newSet();

for_ij_do (
m[i * j]++;
);

for_ij_do (
if (m[i * j] >= 2)
appendSet(setA, newPair(i, j));
);
/* 亞譚: 我不知道這兩個數字是什麼!*/
/* setA->size == 638 */

for_ij_do (
if (findElement(setA, newPair(i, j)))
a[i + j]++;
);

for_ij_do (
if (a[i + j] >= 2 && findElement(setA, newPair(i, j)))
appendSet(setB, newPair(i, j));
);
/* 明歆: 但我也還是不知道這兩個數字是什麼!*/
/* setB->size == 629 */

memset(m, 0, sizeof(int) * UPPER * UPPER);

for_ij_do (
if (findElement(setB, newPair(i, j)))
m[i * j]++;
);

for_ij_do (
if (m[i * j] == 1 && findElement(setB, newPair(i, j)))
printf("%d %d\n", i, j);
);
/* 亞譚: 喔!那我知道那兩個數字是什麼了! */
/* 明歆: 喔!那我也知道那兩個數字是什麼了! */

destorySet(setB);
destorySet(setA);

return 0;
}
兩篇相關的討論
http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/226
http://hoamon.blogspot.com/2007/03/cmclass.html
總算是想出來了... ^o^
Source Code 放在 http://fd.idv.tw/tux/CMClass.tar.bz2
因為不知道 C 上面有什麼 Set 的相關函式, 所以就自己硬幹一個簡易版出來... XD
另外... 為了把 Source Code 貼到 Blog 上, 用到了一段 command
cat main.c | sed -e 's/</\&lt;/g' | sed -e 's/>/\&gt;/' | less
如果有程式有辦法把 Source Code 轉成 HTML 外加彩色應該會很方便好用吧!?
張貼留言