חידת C

[אורן בקר]

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);}

א. האם מישהו יכול לגלות מה עושה הקטע הזה (מהי משמעות הפלט ביחס לקלט)?

ב. להוכיח את זה?
(יש הוכחה חביבה לעניין)

אורן.

[שלוימו]

כותרת: בא לך לעשות את הקוד קצת יותר ברור?? ממש נורא ככה

[אורן בקר]

כותרת: בסדר, למרות שיש לזה סיבה
שאותה יבין מי שיפתור, למרות שהפורום הרס את הצורה המקורית של זה

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);
}

[דניאל ק]

כותרת: פתרון חלקי(מאוד) + כמה הרהורים …
הלולאה רצה על כל המספרים מ1 ועד 2 בחזקת n(מינוס 1).
על כל ערך כזה, היא מחשבת
Z = מיקומה של הסיבית הדלוקה הראשונה מצד ימין(אם מתחילים לספור מ1).
out2 – מכבים את הסיבית הדלוקה הראשונה מצד ימין, ומוצאים את שארית החלוקה ב3.
out3- מוסיפים למספר את ערכו של הסיבית הראשונה שדלוקה מצד ימין, ומוצאים את השארית החלוקה ב3.

קל להיווכח שב Z3
y – 2^(z-1) = out2
y + 2^(z-1) = out3
ומכאן ש
out 3 – out 2 = 2^z
out 2 + out3 = 2y
(כולם modulo 3 כמובן).

הרהורים:
למה דווקא מודולו 3? הקלט הוא N, לא Y… *נראה* שכל איטרציה כזאת עומדת בפני עצמה, אז למה רצים על כל הערכים מ1 עד 2 בחזקת N(מינוס 1), ולא קולטים ישר ערך Y?

מקווה שהפורום לא יהרוס לי לגמריי את המשוואות…

[אורן בקר]

כותרת: ההבהרות נכונות, מה עושה התוכנית?
יפה, זאת התחלה טובה, והתשובות להרהורים שלך יכולות להוות רמזים עבים מאוד לפתרון.

[דניאל ק]

כותרת: אהבתי…
א. הקוד פותר בצורה איטראטיבית את הבעייה הידועה של מגדלי
האנוי…
out1 – איזה דיסקית מזיזים(כשהם ממוספרים מהקטן לגדול).
out2 – מאיזה עמוד מזיזים
out3 – לאיזה עמוד מזיזים.

It is said that after creating the world God set on Earth three rods made of diamond and 64 rings of gold. At the creation they were threaded on one of the rods in order of size, the largest at the bottom and the smallest at the top. God also created a monastery close to the rods. The monks´ task in life is to transfer all the rings onto another rod. The only operation permitted consists of moving a single ring from one rod to another, in such a way that no ring is ever placed on top of another smaller one. When the monks have finished their task, according to the legend, the world will come to an end.

Brassard and Bratley (1988, p. 64)
על ההוכחה ללמה זה נכון אני עדיין עובד…

[דניאל ק]

כותרת: טוב… אז מנסים להוכיח..
את האלגוריתם עצמו – אני אפילו לא אנסה להוכיח… אבל עקרונית הצורת פתרון לבעית המגדלים היא כזאת –
נסמן את הטבעות מן הקטן אל הגדול במספרים 1 עד N. אם הטבעת היא אי-זוגית, היא תמיד תזוז מ0 ל 2, מ2 ל 1, ומ1 ל 0. אם היא זוגית, היא תזוז בכיוון הפוך: 0 -> 1 -> 2 -> 0.
את הרצף הזוגי אפשר לבטא על ידי הביטוי: 0,1,2,0,1,2 = i%3
הרצף האיזוגי: 2i%3 = 0,2,1,0,2,1

על מנת לפתור את הבעיה, נריץ את האלגוריתם הבא, עד שנגיע לפתרון:
1. הזז את טבעת מס 1(על פי הרצף של מספרים איזוגיים)
2. הזז טבעת בין שני העמודים האחרים(שטבעת 1 לא נמצאת עליהם). כאשר רצף ההזזה הוא בהתאם למספרו הסידורי של הטבעת(זוגי / אי זוגי).. מי שבאמת רוצה הוכחה לזה, יש באינטרנט…

ברור לפי האלגוריתם שכל מהלך y איזוגי מזיז את טבעת מס 1..
כאשר y=1, הדיסקית מועברת מ0 ל 2, כאשר y = 3 הדיסקית מועברת מ2 ל 1,וכו´… בצורה כללית, במהלך מס´ y, הדיסקית מועברת מ
%3(y-1) ל %3(y+1).

עבור מהלך שמספרו y זוגי, אך מזיזים טבעת שמספרה אי זוגי, אנחנו למעשה מעבירים את הטבעת באותו רצף של טבעת מס´ 1, מהעמוד הבא בתור אחרי העמוד שאליו הועבר טבעת מס´ 1 -> מעמוד %3(y+2) ל %3(y+4), וזה שקול ללהעביר מ(y-1) ל (y+1) – מכאן שאפשר תמיד להתייחס להעברת טבעת שמספרה אי זוגי כאל העברה מ(y-1) ל (y+1) (כל זה מודולו 3 כמובן).
בדרך דומה, העברת טבעת זוגית תעשה מ%3(y+1) ל %3(y-1)..

בשל האופי הרקורסיבי של הפתרון, מיקומה של הסיבית הדלוקה הימנית ביותר במספר המהלך, הוא גם מספרו של הטבעת שצריך להזיז בשלב זה.
נקודה זו ניתנת להמחשה על ידי דוגמה קצרה:
כדי להזיז מגדל בגובה 1, מזיזים רק טבעת אחת – סיבית אחת דלוקה.
כדי להזיז מגדל בגובה 2 – צריך להזיז קודם את הראשונה(סיבית מספר 1), אח"כ את השניה, ואח"כ שוב פעם את הראשונה..
מגדל בגובה 3 – עושים את מה שעשינו עם 2, אח"כ מזיזים את הטבעת מס´ 3(זהו המהלך הרביעי, וסיבית מס´ 3 היא הסיבית הדלוקה הימנית ביותר) ואח"כ שוב פעם מה שעשינו עם 2…

ועכשיו לכמה הנחות שנשתמש בהם(אפשר להוכיח בקלות עם אינדוקציה, אין לי כוח! ):
2 בחזקת מספר זוגי מודולו 3 = 1
2 בחזקת מספר אי זוגי מודולו 3 = 2

מכאן שעבור ערכים אי זוגיים למספר Z ניתן לשנות את הביטויים
%3(y-1) ל y – 2 ^ (Z+1) mod 3
ו
%3(y+1) ל y + 2 ^ (Z+1) mod 3
ועבור ערכים זוגיים ניתן לשנות את הביטויים:
%3(y+1) ל y – 2 ^ (Z+1) mod 3
ו
%3(y-1) ל y + 2 ^ (Z+1) mod 3

מכאן שאם Z מכיל את מספרה של הטבעת שצריך להזיז במהלך מספר Y(ולמעשה, מיקומה של הסיבית הדלוקה הימנית ביותר בערך Y), אז אנו מזיזים את הטבעת ממקום:
y – 2 ^ (Z+1) mod 3 ל מקום y + 2 ^ (Z+1) mod 3
נכון למקרים שבהם Z זוגי או אי זוגי.

כפי שכבר הראתי בהודעה הקודמת, הביטוי
y – 2 ^ (Z+1) mod 3 שקול לביטוי %3(y&y-1), שקול לout2
והביטוי:
y + 2 ^ (Z+1) mod 3 שקול לביטוי %3(y|y-1)+1), שקול לout3

מ.ש.ל
(תסלחו לי עם השמטתי איפה שהוא את הביטוי mod 3, אבל נורא קשה לכתוב משוואות בפורום הזה), ואם התעצלתי להוכיח משהו… אם זה באמת חשוב למישהו, גם את זה אני אעשה.. למרות שזה בעיקר פיתוח נוסחאות, משימה לא טריוויאלית בכלל בפורום הזה..

[מאת]

תגובות