חידה נחמדה:

[עידו123456]

הקשר

הקשר הוא שזה בדיוק מה שוירוס עושה - הוא מתייחס לקוד שלו עצמו בשביל ליצור עותקים של עצמו. אני לא יודע VB אז כך שאני לא יכול ליצור תוכנה כזאת אבל הינה הדרך הכללית ליצור תוכנה שמדפיסה את עצמה כפי שרואים ממשפט הרקורסיה:

סימונים: אם X תוכנה אזי <X> הוא התיאור של התוכנה נגדיר תוכנה Q שלכל קלט w מדפיסה את <Pw> כאשר Pw היא תוכנה המדפיסה את w ועוצרת. <Pw> היא התיאור של התוכנה. Q תפעל כך: לכל קלט w נבנה תוכנה Pw אשר: - מוחקת את הקלט - כותבת את w - עוצרת Q תחזיר את <Pw> כעת נגדיר את SELF, ל SELF שתי פרוצדורות: A,B כאשר קודם A רצה ואז B. A תדפיס את התיאור של B B תדפיס את התיאור של A A מקבלת מראש את התיאור של B וכל מה שהיא עושה זה פשוט להדפיס את התיאור הנ"ל (A היא בעצם התוכנה P<.B> B תקרא את התיאור של עצמה מהפלט של A ואז תריץ את Q על תיאור זה בשביל לקבל את הקוד של <.P<.B וכפי שראינו בסעיף הקודם <.A=P<.B. בנוסף B תכניס גם הוראות כלליות לקוד כמו "תריץ את A ואז את B" לסיכום, SELF פועלת כך: 1) היא מריצה את הפרצ' A שכותבת את התיאור של B 2) מריצה את B שקוראת את הפלט <B.> מהפרוצדורה הקודמת וכותבת לפני פלט זה את

<P<.B>> = <.A.>​

בנוסף, B מוסיפה הוראות של להריץ את A ואח"כ את B. אני לא חושב שיש כאן משהו שמונע מאיזשהי שפת תכנות בסיסית לממש את הפסאודו-קוד הזה. כל מה שצריך זה יכולת קריאה/כתיבה וקריאה לפרוצדורות.

 

[ahardon]

יפה, אבל...

אפשר לעשות את זה הרבה יותר פשוט.

 

[vinney]

לא ברור לי

אתה מדבר על הקוד המקומפל או על קוד המקור? כי קוד מקומפל זה לא בעיה, וככה באמת הוירוסים עובדים, אבל השאלה היא על קוד מקור... והרעיון הוא לא לקרוא אותו משום מקום...

 

[ahardon]

אפשר בפסקל

 

[ahardon]

זאת המקורית

והדבר שקן תומפסון מדבר עליו ומדגים במאמר... אני רק סיבכתי את זה קצת...

 

[DadleFish]

לא יודע מי זה קן תומפסון,

אני קיבלתי את החידה הזו בתור שאלת בונוס באחד המבחנים בקורס תכנות.

 

[DadleFish]

אהההה נזכרתי מי זה ../images/Emo6.gif

 

[dragonight4]

מה אתם מסתבכים

התשובה הפשוטה זה תוכנית ריקה, 0 בתים. זה מקיים את כל התנאים, והיא קצרה ככל האפשר.

 

[DadleFish]

זו לא תוכנית.

 

[the new L]

נצל"ש - עוד חידה קטנה

לקוחה מראיון עבודה: נתון טקסט כלשהו באורך N. כתוב אלגוריתם (או תוכנית, איך שבה לכם) שמוצא את המילה שמופיעה הכי הרבה פעמים בטקסט ופועל בסיבוכיות

O(N)​

 

[ahardon]

תשובה

PHP היה פה נוח:

function commonword($text){ $text.=" "; $len=strlen($text); $word=""; for($x=0;$x<$len; $x++){ if(($text[$x]==' ') && (!empty($word))){ if(!isset($words[$word])) $words[$word]=1; else $words[$word]++; $word=""; } else $word.=$text[$x]; } $x=0; foreach ($words as $word => $size){ if($size>$x){ $x=$size; $biggest=$word; } } return $biggest; }​

 

[the new L]

../images/Emo31.gif

הפיתרון שלך עובד למיטב הבנתי בסיבוכיות של nlogn ולא בסיבוכיות של O. תנסה להבין למה...

 

[ahardon]

למה?

הוא עובר פעם אחת על הקלט, ופעם אחת על המערך שיצר, אז זאת סיבוכיות

O(2n)​

במקרה הגרוע.

 

[the new L]

כן, אבל

השורה הזאת:

if(!isset($words[$word])) $words[$word]=1; else $words[$word]++;​

לוקחת זמן של logn כי אתה צריך לחפש את המילה בעץ שלך...

 

[ahardon]

הפחדת אותי

אתה רוצה להגיד לי ששואלים כאלה דברים בראיונות עבודה? חשבתי על זה חצי שעה רצוף ואין לי פתרון, אני לא רוצה לחשוב מה היה קורה אם הייתי מקבל את השאלה הזאת בראיון...

 

[the new L]

../images/Emo58.gif הפיתרון ../images/Emo58.gif

נבנה עץ שערכיו הם אותיות. בכל פעם שאנחנו עוברים על מילה חדשה נעבור משורש העץ לעלים של האותיות השונות (למשל עבור המילה hello, נתחיל בשורש, נחפש את הבן שלו עם האות h ונוסיף לסכום שלה ערך 1. נחפש את הבן של האות h עם הערך e ונוסיף לסכום שלו ערך 1, נעבור לבן שלו עם האות L ונוסיף 1, נעבור לבן של l עם האות L ונוסיף לסכום שלו 1 וכן הלאה...). לסיום נסרוק את העץ (שמכיל פחות מ n בנים), ונמצא את העלה עם הערך המקסימלי. נעלה מהעלה עד השורש, ונקבל את המילה שהופיעה הכי הרבה פעמים.

 

[DadleFish]

הערות

ראשית, לא ציינת שמילים מופרדות ברווחים. שנית, "נבנה עץ שערכיו הם אותיות". אם הבנתי אותך נכון, זה עץ בגודל 26 בחזקת N (נניח שאין חשיבות ל-CASE של האותיות), כאשר N הוא אורך המילה הארוכה ביותר. אני צודק? כי אם כן, עץ כזה בעומק של 8 אותיות בלבד (לא גדול במיוחד) יכיל בסה"כ 208,827,064,576 צמתים. אם נניח שכל צומת היא בעלת 12 בתים, זה בעצם אומר שהאלגוריתם צורך 2505924774912 בתים, שהם 2447192163 KB, שהם 2389836 MB לערך, שהם 2333 GB. במילים אחרות, על מנת לבנות עץ כזה, אתה צריך מחשב שיש לו למעלה מ-2000GB זיכרון, שלא לדבר על הזמן שיידרש לך להכין עץ כזה. עכשיו, נניח שלא הבנתי אותך נכון, ושהעץ נבנה תוך כדי הפעילות של האלגוריתם. זה בעצם אומר (O(N פעמים חיפוש ובניית צמתים בתוך העץ. עומק העץ הוא (O(logN (כאשר N גודל הקלט כולו), ולכן האלגוריתם ירוץ ב-(O(NlogN.

 

[cyberia2ooo]

אממ

אם העץ נבנה בזמן ריצה, אז לוקח O(N) בשביל הבניה ועם עוברים על כל העלים (כלומר הצמתים בלי הבנים) המעבר הוא גם O(N) אז איפה הבעיה O(2n) זו הסיבוכיות

 

[the new L]

אתה מניח בחישוב שלך

של ה-26 בחזקת n שכל מילה אפשרית באורך n אכן קיימת בטקסט שלי, מה שכמובן לא נכון. אולי אני אסביר קצת על איך העץ נראה. למשל אם הטקסט שלי הוא :

"hi hey hello" then we will have only one root node - h, with the value 3 it will have 2 sons, i = 1 and e = 2 i will be a leaf. e will have 2 sons: y = 1 and l =1 y will be a leaf. l will have one son, l = 1 l will have one son, o = 1 o will be a leaf​

מקווה שעם הדוגמה זה יותר ברור למה הבנייה של העץ היא בזמן לינארי, וגם הגודל שלו הוא לינארי

 

[DadleFish]

טוב, בסופו של דבר הבנתי לבד מה

שניסית להסביר. אתה רץ על כל הטקסט ובונה את העץ, כשלכל אות אתה לא צריך להתחיל מתחילת העץ אלא יש לך את ה-NODE הנוכחי. יפה