התגובות שלי בפורום
-
תגובות
-
כותרת: סימון,
תוכנית יפה, אבל ההוכחה על ידי בדיקת כל האופציות תהיה קצת יותר בעייתית אם תצטרך להוכיח שאי אפשר להגיע למספר 234234234234324121
באמצעות 100000000000000000 מטבעות.כותרת: אני נאלץ להודות בטעותי.
השיטה עליה חשבתי(שימוש בXOR במקום חיבור וחיסור מודולרי), פועלת רק כאשר מספר הצבעים הוא חזקה של 2.אז קבלו את התנצלותי על ההטעיה.
כותרת: אני חושב שהפתרון שלה די תקף לכל מספר צבעים
פשוט במקום לעבוד ב MOD 2, עובדים בMOD N.
וכן, כל הכבוד
כבר חשבתי שאנשים ויתרו על החידה.אבל אם בכל זאת מנסים להוסיף לחידה מימד נוסף – מה עושים אם הגמדים לא יודעים איך לבצע חיבור או חיסור מודולארי?(ולא, אי אפשר להסביר להם איך).
כותרת: תשובה לגררר
אפשר. TheWizard כבר ציין את זה.
אני אישית נואשתי מהחיפושים, ומצאתי את הפתרון באיזה אתר(מן הסתם, אני לא אפרסם את התשובה), אבל יש פתרון. אולי יש מקום לפרסם רמז…כותרת: אממממ.. החלק השני הוא למתקדמים
אני כן יכול להצביע על כמה מטבעות שחייבים להיות קיימים(100, 2, 1), ואולי הדרך פתרון מתבססת על לוגיקה דומה, או שאולי צריך לכתוב איזה תוכנית Bruteforce(אבל אז אין הרבה עניין בחידה, זה סתם לתת למחשב לטחון אופציות).אני כן יכול להצביע על עובדה מעניינת אחרת בכל נושא המטבעות, אם נפתח סוגרים בביטוי הבא:
(1 + x + x^2 + x^3 + x^4 + x^5 …)(1 + x^5 + x^10 + x^15 + x^20 + x^25 …)(1 + x^10 + x^20 + x^30 + x^40 + x^50 …)(1 + (1 + x^25 + x^50 + x^75…)(1 + x^50 + x^100…)אז המקדם של
x^100
למעשה אומר בכמה דרכים שונות אפשר להרכיב דולר מהמטבעות הנ"ל.
המקדם של
x ^ 55
למעשה אומר בכמה דרכים שונות אפשר להרכיב 55 סנט מהמטבעות הנ"ל.
(מישהו מבין למה?)בכל מקרה, כל התחום הזה נקרא
Generating functions
ואוהבים להשתמש בו בכל מיני בעיות קומבינטוריות…כותרת: פתרון לחלק הראשון.
אפשר על ידי תוכנית, שתבדוק בכמה דרכים שונות אפשר ליצור דולר, וכמה מטבעות נדרשות בכל דרך(יש 292 דרכים שונות אגב).
ואפשר גם על ידי ההגיון +- לבדוק את זה…1. 100
2. 50 + 50
3. 50 + 25 + 25
4. 25 + 25 + 25 + 25
5. 50 + 25 + 10 + 10 + 5
6. 50 + 10 + 10 + 10 + 10 + 10
על ידי החלפה של מטבע 10 ב2 מטבעות של 5, נגדיל את מספר המטבעות כל פעם ב1, ובשיטה זו נגיע עד 10…
10. 10 פעמים 10.
שוב פעם, על ידי החלפת מטבעות של 10 ב2 של 5, אפשר להגיע עד 20.
20. 20 מטבעות של 5.
מכאן, נחליף מטבע של 5 ב5 מטבעות של 1, מה שיוסיף לנו 4 מטבעות לסכום. כדי לפצות על כך(אנחנו צריכים להוסיף רק מטבע 1), נמיר מטבעות של 5 למטבעות של 10(6 מטבעות 5 בשביל להגיע ל+1, 4 בשביל +2, 2 בשביל +3, ולא נמיר מטבעות של 5, אם צריך להוסיף 4).
נמשיך בפעולה זו, עד שנגיע ל76:
70 מטבעות של 1, ו6 מטבעות של 5.
עתה, אם ננסה להמיר מטבע של 5 לאחדות, לא יהיו לנו מספיק מטבעות 5 כדי להגיע לתוספת של מטבע אחד בלבד(ניתן להמיר רק 2 זוגות מטבעות של 5, ולכן נגיע ל+2, אבל לא ל+1).כלומר – 77 הינו המספר המינימלי שאי אפשר להרכיב בו דולר.
מקווה שהייתי מספיק ברור…
כותרת: עניתי כבר בפורום חידות…
אבל אני אחזור כאן על הפתרון – חיבור מספר זוגי של מספרים אי זוגיים תמיד יתן מספר זוגי – מכאן שאי אפשר להגיע ל25. אפשר גם להוכיח את זה די בפשטות, אבל אני חושב שההגיון כאן מספיק.כותרת: חחחחחחחח, אהבתי
אבל חידה פשוטה למדי…
אתה הרי מחבר סכום זוגי של מספרים אי זוגיים, והתוצאה תמיד תצא זוגית – החידה בלתי אפשרית.כותרת: הופההה….
יוני, אתה מתחיל פה משהו מאוד מסוכן…
ואני מציע לך לא להתחיל עם הויכוח Linux/windows אלא אם כן אתה באמת מודע למה שאתה הולך להתחיל כאן.אני בכל מקרה, אגן במלוא עוזי על המערכת שנותנת לי באמת לשבת ולפתח, ולא להיות עסוק בTweaking כל הזמן(הגזמה דרסטית כמובן, אבל זאת רק דוגמה לאיך הדיון הזה יתנהל, על סמך אלפי דיונים כאלה בעבר).
כותרת: מחפש בלונדינית שופעת בגילי…
אחי, אני לא חושב שזה פורום מתאים לחפש עבודה… מדובר בכל זאת בתחרות תכנות לתלמידי תיכון. בכל מקרה? ממתי מחפשים עבודה דרך פורומים???
לא עדיף להסתכל במודעות דרושים?
