Re: [閒聊] 臉書在找人

[yauhh (喲)]

※ 引述《sandy4444 (質樸)》之銘言：
: 謝謝大大的分享
: 但我有些問題想問
: 我是資工系大三的學生 也想應徵看看intern // 是類似summer intern 的那種??
: (之前一直以為是不可能接觸 沒想到真的可以interview)
: 不敢相信申請link-in 就可以投fb履歷 > <
: 但是想問文中的 puzzle 是什麼?!?!??!
: 先分享那題做法
: int answer(分數陣列,N)
: {
: 運算陣列初始歸零;
: 分數陣列排序小到大;    //M個
: 運算陣列[0] = 1;
:         迴圈 i 從 0 跑到 M
:                 迴圈 j 從 分數陣列[i] 跑到 N
:                         運算陣列[j] += 運算陣列[j-分數陣列[i]];
: return 運算陣列[N];
: }

少寫了一些細節,這個題目是除了組合之外,還加上判斷.

應該是先做一個產生分數陣列元素數目的 0 1 挑選情況:

void print_arr(int array[], int len) {
  for (int i=0; i<len; i++)
    cout << array[i] << ' ';
  cout << endl;
}

void comb_array(int len, int result[], int len1) {
  if (len == 0) {
    print_arr(result, len1);
    return;
  }
  if (len < 0) return;
  result[len-1] = 0;
  comb_array(len-1, result, len1);
  result[len-1] = 1;
  comb_array(len-1, result, len1);
}

然後可以把 print_arr 印出 0 1 情況的部份改成加總判斷:
  if (len == 0 && SumupAs(array, len1, choose, N)) {
    print_arr(array, len1, choose);
    return;
  }
所以把上面的 comb_array, print_arr 變形為以下程式.

#include<iostream>
using namespace std;

bool SumupAs(int array[], int len, int choose[], int N) {
  int sum = 0;
  for (int i=0; i<len; i++) {
    if (choose[i] == 1) sum += array[i];
  }
  return (sum == N);
}

void print_arr(int array[], int len, int choose[]) {
  for (int i=0; i<len; i++) {
    if (choose[i] == 1) cout << array[i] << ' ';
  }
  cout << endl;
}

void PossibleArray(int array[], int len, int choose[], int len1, int N) {
  if (len == 0 && SumupAs(array, len1, choose, N)) {
    print_arr(array, len1, choose);
    return;
  }
  if (len < 0) return;
  choose[len-1] = 0;
  PossibleArray(array, len-1, choose, len1, N);
  choose[len-1] = 1;
  PossibleArray(array, len-1, choose, len1, N);
}

int main() {
  int array[] = {2, 3, 7};
  int choose[] = {0, 0, 0};
  PossibleArray(array, 3, choose, 3, 9);
}


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.65.204
→ zekewang:這是啥?? 之前的組合題目嗎...
→ zekewang:這種題目 離散學的好...做法好幾樣....重點是數學學得好
→ zekewang:其實這種大公司~多半要求電腦科學基礎要很好
→ zekewang:雖然都說要求實做要好...但是這類的實作都架構在學科強
→ yauhh:要不然你覺得是什麼? 回文引文內寫得明明白白呀
→ yauhh:蠻多人一下子就衝DP,我覺得蠻疑惑,有沒有將基本解決辦法講個
→ yauhh:所以然呢? 如果沒先確定能怎麼解,突然說DP或DFS就能解了嗎?
→ yauhh:至於學科好不好,再說啦,說穿了不是學科厲害的才會解這題目.
→ yauhh:是人都可能思考解決問題. 用不著穿鑿附會,高來高去.
推 Huangs:yauhh 大這版的答案真是經典！！
→ zekewang:本來就是學科學的好就會解.....
→ zekewang:這有什麼嗎??? 大驚小怪...
→ zekewang:就算學科不好也會解..至少學科學的好..解的也漂亮..
→ yauhh:有大驚小怪嗎?
→ yauhh:不要閒扯一堆泛論,聽起來很無聊
→ zekewang:這種問題本質就是數學問題..不扯數學扯什麼?語言嗎??
我看了你這段反應實在覺得不舒服. 今天我並沒有反對你任何一句話,
只告訴你說:不要閒扯.

這篇文只是前文有一個題目,所以我在這裡給一個答案, 不過如此而已.

但你卻扯到別處說,哎呀,都是離散數學學得不錯的人才比較會解;
離散數學學得好,作法就好幾種...

這種話看起來很無聊耶,你愛講,那麼你為什麼不自己當場在這裡給我們介紹介紹所謂
好幾種離散數學的作法呢?

第二點,在工作的場合,你身邊的同事不管學得好或學得不好,你都沒有本事只根據學識
好或不好來決定你要不要跟他好好相處. 真的有唸過書的人,不會這麼愛分別彼此程度.
說穿了,數學或語言,不過就是鑿子或榔頭,你愛用就用啊,強調一個鑿子很重要是幹嘛?
從來沒看過誰拿著鎚子說自己使鎚的工夫好,好到飛上了天了這個樣子.

而且甚至你還冒出了"語言"這個詞,那你看看我這篇用了哪一種語言呢?
你寫"數學"二字寫了好幾次,沒看過你拿出什麼數學式來解解這個題目.
而我"語言"二字一次都沒出現,你卻突然要放這一槍,這真是有趣啊  = =

推 ledia:如果說像是這邊的窮舉的話, 的確比較無關數學, 語言熟練度吧
→ zekewang:這也是假設....題目本身就是一題數學題..用語言實作出來
→ zekewang:就是這麼簡單......不用limitation設一堆...
→ zekewang:如果題目出的語意不清..或是隱含一堆假設..那是題目不對
→ zekewang:在學校考試的時候..做題目也不會對題目作諸多假設...
→ zekewang:何以一出社會看到題目就是一堆假設....
→ zekewang:總之題目不清楚是題目問題.題目夠清楚就不用假設一堆..
→ manlike:其實看到這些討論就知道等級在哪了~ 根本不需要吵 XD
→ manlike:每個人的等級有落差根本難以討論...
→ manlike:我想這也是為何fb會考這總題目, 等級不同很難 co-work...
→ manlike:                      種
→ yauhh:那zekewang你說說這題目哪裡題意不清?
→ yauhh:事實上,工作的時候,很多題意不清的是經手人最後自己釐清的.
→ amos6064:嘿嘿樓上這句中肯
→ gmoz:推
→ lovdkkkk:DP 也是基本解決辦法呀 對熟 DP 的人來說
→ lovdkkkk:像我不熟 想到背包去 想複雜了 半小時邊聊邊做穩死
→ lovdkkkk:那個大陸的 簡簡單單十分鐘... 我想這就是他們要的吧
→ yauhh:因為DP是籠統概括的詞. 如果你可以找到一套有系統,制式的DP
→ yauhh:建構格式,就會很快. 但是似懂又對DP感覺模糊還要跩名詞,
→ yauhh:那要實際做還不知道要等哪天才有.
→ yauhh:我覺得這篇作法並不是窮舉,而是backtracking,有斬掉旁枝末節
→ yauhh:而且作法明明也是數學作法,有加,有等於
→ yauhh:我倒很知道有人所謂數學方法用在此是什麼樣子,秀出來看看吧
※ 編輯: yauhh           來自: 61.231.65.204        (02/27 22:23)
→ manlike:M(i,n) = M(i-1,n-Si) + M(i-1,n)   for n>0
→ manlike:         1                        for n=0
→ manlike:         0                        for n<0
→ manlike:         1                        for i=0 and n=0
→ manlike:         0                        for i=0 and n!=0
→ yauhh:那這個式子變成程式是什麼樣子?
→ manlike:就是兩個for loop, 把一張表填完, 答案都在裡面..
推 Huangs:式子應該是 M(i,n) = M(i,n-Si) + M(i-1,n)
→ Huangs:不然每一種面額只能用一次。
→ manlike:喔, 我是用不能重複選的想的 XD
推 Huangs:是不能有重覆的組合，但同一個面額可以重覆用
→ Huangs:每個面額限用一次，總合稍大就湊不出來了。
→ yauhh:不是喔,如果你要填表,要把握的是把求過的子算式過程節省下來
→ yauhh:那就不是在講會不會數學了,而是程式技巧要多一點.
→ yauhh:假如之前計算過1+2,後面的算式有包含到1+2就要參考到那一格,
→ yauhh:計算過程就節省了一步.
→ zekewang:唉~~居然這樣就生氣...唉
→ zekewang:你一生氣...我就要告訴你怎麼解??...
→ zekewang:這一題不算是太難的題目....一大堆人會解...
→ zekewang:不太難的題目還那麼在意別人的解法...
→ zekewang:跟人相處也不是看學科學的好不好來決定與人相處的
→ zekewang:不管是工作上或是單純朋友或同學....結果還能扯到人際上
→ zekewang:唉...真不知道該怎麼說......看來有其他東西比學科更重要
→ zekewang:那現在這篇可能要講到人際關係了...不適合講數學和語言
你看,講了大半天還不是一大堆你自己的閒扯出來的東西. 回頭來看,原來的問題是說在
面試時與人當面討論一個問題並完成程式, 這又跟你立即歸納的數學,語言和人際關係
有什麼關係? 別人寫一個文章內容不在這個方面,你跑來歸納個半天,分析個半天,
然後自己感嘆起來,仍然是無聊啊! 重點是,你的離散解法好幾種呢? 怎不介紹?
→ yauhh:manlike,也許你認為給出這個式子然後填表就可以完成比較好的
→ yauhh:程式解法. 不過,DP的填表只是一種解題策略. 你仔細看,我的
→ yauhh:程式有重複引用子程序所產生的結果,求加總這一段也可以變形
→ yauhh:為填表的版本,就可以變成DP並享有速度改善的優勢.
※ 編輯: yauhh           來自: 61.231.66.117        (02/28 11:10)
→ zekewang:看吧....又在扯東扯西了...我只說數學...什麼人際關係
→ zekewang:是你說的..是誰在回文扯什麼同事程度好不好跟相處問題
→ zekewang:只會把別人的話加油添醋...生氣就生氣還要加油添醋...
→ zekewang:加油添醋就算了...硬要別人回答你的問題....
→ zekewang:我只說這題是數學問題...本來就是數學問題...
→ zekewang:這樣就生氣還要別人推導程式給你看....
→ zekewang:唉...說真的啦....懶得回你了....繼續生氣就生氣
→ zekewang:想要好幾樣的解法就自己導吧
→ zekewang:導不出來我也不太想回你了.
→ zekewang:然後這種生氣又跳針的人一定會說
→ zekewang:"看吧...要他導數學式就說不回應了"...
→ zekewang:這種人真是到處都有阿....好...到此為止..繼續生氣吧...
好好一段數學的東西擺在你眼前,你沒看見,卻滿口說數學數學,講得好像我的解
就不是數學解.

其實我的程式就是數學的東西,用式子表達如下:
    PArray(a,i,j,n) = { a[i] ∪ x | x 屬於 PArray(a,i+1,j,n-a[i])
                                   且 a[i]+sum(x) = n }
                      ∪ { x | x 屬於 PArray(a,i+1,j,n)
                                   且 sum(x) = n }

第二點,我並沒有說這一題 "不是數學問題". 是你自己一直在搞一種對立立場.

       我也沒有多費唇舌去講出它究竟 "是不是" 數學問題.

       一個是這樣的東西,你還要花時間花心力強調 "它是", 會不會太浪費人生?

我覺得你很可憐,霸佔著別人的文章,在推文中一直嘴砲你自己那一套.

我看你推文的行數都快要比我的本文行數更多了...

可是我根本沒把你嘴砲當一回事,該給的解答全給了.

經過這些討論,我覺得我的實力比你罩.

另外,至於你說我生氣,我倒覺得,是因看你搞笑及無事生非,而感到困擾的感覺居多.

※ 編輯: yauhh           來自: 61.231.66.119        (02/29 10:50)
→ zekewang:作者: choufeng (資訊業討論專版) 看板: Soft_Job
→ zekewang:標題: [公告] yauhh 板友發言不當 警告乙次
→ zekewang:時間: Tue May 18 22:05:14 201
→ zekewang: 作者  yauhh (喲)  看板  Soft
→ zekewang:標題  [閒聊] 抱歉
→ zekewang:時間  Tue May 18 22:34:42 2010
→ zekewang:看你之前文章到處跟人吵架...然後又道歉...可笑
→ zekewang:還需要跟你吵嗎???還有不要回文還要寄信給我...
→ zekewang:這種信看了真是礙眼喔....y
→ TonyQ:兩邊都冷靜一下不要吵架，文章鎖定處理，討論請就事論事