התגובות שלי בפורום
-
תגובות
-
כותרת: תודה רבה!
היה מאוד נחמד להתחרות בארבע תחרויות קודגורו (ובמיוחד בשתיים האחרונות).אני כבר לא אוכל להתחרות בקודגורו הבא (זקנתי…), אבל אני מקווה שאני אוכל לשמור על קשר כלשהו עם התחרות.
בהצלחה לכל המתמודדים בתחרויות בעתיד. רק תזכרו שלהיות *קוד*גורו זה לא הכל (אבל זה עוזר)…
להתראות (עם חלק מכם כבר בטקס..) ותודה רבה למארגנים,
אורן.כותרת: שאלה 22
לדעתי התשובה היא שיש רק אפשרות אחת לספרת העשרות והיא 7.17^7 mod 100 = 73
17^10 mod 100 = 49M = 17^(10n+7) mod 100 = (17^10)^n * (17^7) mod 100 =
49^n * 73 mod 10049^2 mod 100 = 1
עבור n = 2k
M = 49^(2k) * 73 mod 100 = (49^2)^k * 73 mod 100 = 1 * 73 = 73עבור n=2k+1
M = 49^(2k+1) * 73 mod 100 = 49 * 73 mod 100 = 77בשני המקרים ספרת העשרות היא 7
כותרת: פתרון (לאלי)
השארית מחלוקה בתשע של כל ביטוי שמגיעים אליו בצורה הזו שווה לשארית מחלוקה בתשע של סכום כל הספרות שבביטוי, כלומר לשארית של 45 מחלוקה ב 9, אפס. לכן, לא ניתן להגיע ל 100 בצורה זו.ניתן להכליל ולומר שבבסיס b, כאשר b זוגי, כל ביטוי כנ"ל המורכב מכל ספרה בבסיס בדיוק פעם אחת, יחלק את b-1.
אורן.
כותרת: הסבר
אלגוריתם דייקסטרה מוצא את מסלול הקצר ביותר בין שני צמתים על גרף העובר דרך קשתותיו.כדי להבין איך הוא עובד, מומלץ להשתמש בדימויים:
אתה נמצא בנקודת המוצא, ממנה יוצאות מספר קשתות. עבור כל קשת, אתה שולח סוכן שהולך בה, מנקודת המוצא עד לסוף הקשת. כל הסוכנים הולכים במהירות שווה *בו זמנית*. כאשר סוכן מגיע לצומת (כשהוא מגיע לסופה של הקשת), הוא מתפצל למספר סוכנים, אחד עבור כל קשת, שצועדים לכיוון צידה השני של כל קשת.
אם תריץ סימולציה כזו, יווצר מצב בו בזמן t, ימצא סוכן בכל נקודה על המפה (נקודה יכולה להיות איפהשהו על קשת או בקצוותיה) אליה יכול סוכן ההולך במהירות הנ"ל להגיע בדיוק בזמן t. לכן, ברגע שיגיע סוכן לנקודת היעד בפעם הראשונה, תוכל לדעת שהמסלול שהוא עשה אליה הוא הקצר ביותר (כי אם קיים מסלול קצר יותר, היה מגיע אל נקודת היעד סוכן כלשהו מוקדם יותר).
אלגוריתם דייקסטרה מתבסס על הרעיון הנ"ל, אך במקום לקדם את הסוכנים באופן רציף על הקשתות, דייקסטרה מתקדם ישירות לזמן הקרוב ביותר בו יגיע סוכן כלשהו לצומת כלשהי. מכיוון שמהירויות הסוכנים שוות וקבועות, הסוכן הבא שיגיע לצומת כלשהי, הוא הסוכן שאורך המסלול הכולל שהוא עושה מנקודת המוצא, עד לצומת אליה הוא עתיד להגיע הוא הקצר ביותר. את הסוכן הנ"ל מפצלים למספר סוכנים כמתואר לעיל ומוסיפים אותם למאגר הסוכנים. האלגוריתם מסתיים כאשר הצומת הקרובה ביותר אליה יגיע סוכן כלשהו היא צומת היעד. הדרך אותה עשה הסוכן הנ"ל היא הדרך הקצרה ביותר אליה.
כדי לממש את האלגוריתם, יש צורך במבנה נתונים ממנו יהיה קל לשלוף את האיבר בעל המפתח הנמוך ביותר (שמייצג את אורך המסלול הקצר ביותר) ולהכניס איברים חדשים. ניתן להשתמש ב"ערימה" (heap) שמיועדת בדיוק לצורך הנ"ל. כך, מאותחלת הערימה עם איבר יחיד המייצג את המסלול חד הצומת [נקודת יעד] והאורך 0. בכל איטרציה של האלגוריתם שולפים את האיבר מראש הערימה, ומוסיפים במקומו איבר אחד עבור כל קשת היוצאת ממנו, המכיל את המסלול שעשה האיבר שהוצאנו ועוד הקשת המתאימה בה ילך הסוכן, ותוספת האורך המתאימה לפי אורך הקשת. האלגוריתם מסתיים, כאמור, כאשר הצומת האחרונה במסלול של האיבר הנמצא בראש הערימה היא צומת היעד.
כדי לחסוך בזמן, ניתן לסמן את הצמתים שכבר בוקרו בידי סוכן כלשהו כדי לא לבקרם בשנית ע"י אף סוכן.
כדי לחסוך בזיכרון, ניתן להשתמש ברשימות לייצוג המסלולים ולשתף ביניהן את התחלות המסלולים המשותפות לסוכנים שהתפצלו מאותו סוכן אב (במקרה כזה, המסלולים ייתקבלו הפוכים בהכרח, ולכן ניתן לבקש את המסלול מנקודת היעד לנקודת המוצא כדי לקבל את המסלול בסדר הרצוי).הכתובת המצורפת מכילה את מאגר כתביו של דייקסטרה עצמו בנושאים שונים.
בנוסף, למידע נוסף על "ערימות", ראה:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/heaps.html
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Priority-Q/אורן.
כותרת: אני לא חושב שהפתרון צריך להיות כ"כ מורכב
פשוט תעשה XOR בין כל האיברים ותבדוק את ה LSB של התוצאה הסופית. אם היא 0 אז אפשר, אם היא 1 אז אי אפשר.כותרת: השאלה השלישית
תחשוב על זה שהפעולה ADD היא הפיכה, מה זה אומר בקשר לסידור ההתחלתי ולכל סידור שאפשר להגיע אליו ממנו? לאיזה צורה נורמלית אפשר להביא כל סידור התחלתי ואיך אפשר לנצל את זה שיש שלושה מספרים או יותר כדי לקבוע אם הצורה הנורמלית הזאת יכולה להפוך לשורת אפסים או לא?כותרת: פתרון
אוקיי, עבור שני כדורים אני מציע את הפתרון הבא:יהי n מספר הקומות בבניין:
אם n=1, האלגוריתם מסתיים, מצאנו את הקומה ה"קריטית".
אחרת:
חשב את
p=(1+sqrt(8*h-15))/2
(עגל כלפי מטה)
זרוק בקבוק מקומה p.
אם הוא נשבר, הבעיה יורדת למציאת הקומה הקריטית עבור בניין בעל pקומות עם בקבוק אחד (אין ברירה אלא לבצע סריקה ליניארית).
אם הוא לא נשבר, הבעיה יורדת למציאת הקומה הקריטית עבור בניין בעל n-p קומות עם שני בקבוקים (ע"י שימוש רקורסיבי באלגוריתם זה).האלגוריתם הוא אופטימלי ומספר הזריקות המירבי שעלול להידרש הוא p (עבור מספר הקומות המקורי).
אציין שלפתרון זה קשר הדוק לפתרון הפשוט לחידת הדחיסה שפרסמתי קודם (זה שמשתמש בשורש)
עבור יותר משני בקבוקים הנוסחה למציאת p מסתבכת, אם היא בכלל קיימת:
עבור שלושה בקבוקים למשל, מציאת p דורשת את פתרון המשוואה:
n^3 – 3n^2 +5n = 6hכותרת: ההבהרות נכונות, מה עושה התוכנית?
יפה, זאת התחלה טובה, והתשובות להרהורים שלך יכולות להוות רמזים עבים מאוד לפתרון.כותרת: בסדר, למרות שיש לזה סיבה
שאותה יבין מי שיפתור, למרות שהפורום הרס את הצורה המקורית של זהmain() {
int z,y,n;
scanf("%d",&n);
for(y=1;(1<<n)-y;y<<=z-1,
printf("out1: %i out2: %i out3:%i.n",
z,(y&y-1)%3,((y|y-1)+1)%3),y++)for(z=1;!(y&1);z++,y>>=1);
}כותרת: החידה נפתרה מתמטית בפורום אורט
הפצתי את החידה בין חברים והיא התגלגלה לשם ונפתרה בפורום החידות:
http://forums.ort.org.il/scripts/forum.asp?forum=219קישור לפתרון: http://forums.ort.org.il/files/219/1604447/9582212.htm
חבל שלא מספיק אנשים מודעים לאתר הזה (קודגורו), כי מתברר שיש מי שיש לו מוטיבציה לפתור חידות כאלו.
