התגובות שלי בפורום
-
תגובות
-
כותרת: אין לי פתרון אנליטי, אבל סימולציה מראה ש:
מספר הבנים נשאר פחות או יותר 50%!אני אמשיך לשבור את הראש איך להוכיח את זה..
בינתיים מצורף הקטע קוד של הסימולציה…double f(int families)
{
srand(time(0));
int GirlCount = 0;
for(int BoyCount = 0; BoyCount < families; BoyCount++) //Each family has one boy, not matter what.
{
for(int tmp = 0; rand() < RAND_MAX / 2; tmp++);
GirlCount += tmp;
}
return ((double)BoyCount) / (BoyCount+ GirlCount);
}כותרת: קטע הקוד
לא אופטימלי במיוחד, אבל בכל זאת עובד.
int MaxFloor(int throws, int balls);
int main(int argc, char* argv[])
{
int Height, balls, throws;
printf("Enter height N: ");
scanf("%d", &Height);
printf("Enter number of balls K: ");
scanf("%d", &balls);
for(throws = 0; true; throws++)
{
if(MaxFloor(throws, balls) >= Height)
break;
}
printf("Worst case number of throws: %dn", throws);
int Max = MaxFloor(throws, balls);
for(int i = 0; i < throws; i++)
{
int Floor = Max – MaxFloor(i, balls);
if(Floor < Height)
printf("%d -> %dn", throws – i, Floor);
}
return 0;
}int MaxFloor(int throws, int balls)
{
if(!throws || !balls)
return 0;
return MaxFloor(throws – 1, balls – 1) + 1 + MaxFloor(throws – 1, balls);
}כותרת: "אציין שלחידה יש קשר ברור לחידת הדחיסה שפרסמתי"
מדהים, אה? 2 שיכורים זורקים בקבוקי בירה מאיזה בניין, ובסופו של דבר מגיעים לאלגוריתם דחיסה.
כותרת: פתרון כללי לK זריקות
אז ככה. העקרון הוא די בסיסי – הקפיצות כל הזמן משתנות, מתוך נקודת הנחה שמספר הזריקות במקרה הכי גרוע צריך להיות קבוע.
הדוגמה של 2 כדורים – על כל פעם שזורקים את הכדור הראשון, מספר הזריקות שאפשר לעשות עם הכדור השני במקרה שהוא נשבר הולך וקטן.
בכמה הוא קטן? בכמות הקומות אליו ניתן להגיע עם K כדורים בT זריקות.את כל זה אפשר לנסח עם נוסחה רקורסיבית יחסית פשוטה:
N = G(K,t( – הקומה המירבית אליה ניתן להגיע, כפונקציה של מספר הזריקות ומספר הכדורים.
כאשר G מוגדר ככה:
G(K,t) = G(K-1,T-1) + 1 + G(K, T-1)
(הפורום מקשה בכתיבת נוסחאות
).
פחות או יותר, מה שזה אומר זה ככה: הקומה המירבית שאליה ניתן להגיע עם K כדורים ב T זריקות, הוא כמו מספר הקומות אליו ניתן להגיע עם T-1 זריקות, בתוספת מספר הקומות שאליהם אפשר יהיה להגיע אם הכדור נשבר, ונותרו לנו רק K-1 כדורים.הדרך מהנוסחה הזאת ועד איזה קומות בדיוק צריך לזרוק מהם קצרה מאוד, אפילו כתבתי תכנית קטנה שתעשה את זה, ביום ראשון אני אפרסם אותה. (או
ולגבי הקטע שמספר הזריקות מגיע ל LOG N, מסתבר שכאשר מגיעים לLOG N, האלגוריתמים(חיפוש כזה וחיפוש בינארי) הם יעילים באותה מידה, אז שיטת הפתרון עדיין נשארת בסדר.
אמרי – לא שמעת על מגדל בבל?? זה לא קצת התגרות באלוהים לבנות בניין בן אינסוף קומות??
כותרת: למיטב ידיעתי אין יותר קצר
כנראה שמאוד מוכרת..
לא ציפיתי שישר על התשובה הראשונה יתנו אותה…בכל מקרה, יש מעבדים שבהם עדיף להחליף את הפקודה
CWD
ב
mov dx, ax
sar dx, 15
כדי לנצל את יכולות המעבד להריץ כמה פקודות בו זמנית, או כדי לעבוד עם אוגר אחר מאשר DX(כמובן שצורה זו של SAR לא תעבוד במעבדים ב8086, אבל לא נורא, האופטימיזציה הזאת גם ככה לא תעזור בהם).ואם כבר הזכרנו
FABS,
אפשר גם לכפול את המספר בעצמו, ואז לעשות שורש.עוד דרכים?
כותרת: נמחק לי התוכן…
אני לא בטוח שאפשר באופן כללי…
החל מ K מסוים(K = LOG2 N ומעלה), השיטה הכי יעילה זה פשוט חיפוש בינארי, ללא קשר לK.
טוב, אז אולי כן אפשר באופן כללי, לכל המספרים שקטנים מ
LOG2 N.כותרת: נמחק לי התוכן…
אני לא בטוח שאפשר באופן כללי…
החל מ K מסוים(K = LOG2 N ומעלה), השיטה הכי יעילה זה פשוט חיפוש בינארי, ללא קשר לK.
טוב, אז אולי כן אפשר באופן כללי, לכל המספרים שקטנים מ
LOG2 N.כותרת: טוב… אז מנסים להוכיח..
את האלגוריתם עצמו – אני אפילו לא אנסה להוכיח… אבל עקרונית הצורת פתרון לבעית המגדלים היא כזאת –
נסמן את הטבעות מן הקטן אל הגדול במספרים 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, אבל נורא קשה לכתוב משוואות בפורום הזה), ואם התעצלתי להוכיח משהו… אם זה באמת חשוב למישהו, גם את זה אני אעשה.. למרות שזה בעיקר פיתוח נוסחאות, משימה לא טריוויאלית בכלל בפורום הזה..כותרת:
אהבתי…
א. הקוד פותר בצורה איטראטיבית את הבעייה הידועה של מגדלי
האנוי…
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 ועד 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?מקווה שהפורום לא יהרוס לי לגמריי את המשוואות…
כותרת: זה לא ממש מתאים להגדרה של חידה…
אבל זה בהחלט קטע קוד מעניין…בכל מקרה, לולאה כזאת קיבלה את הכינוי
Duff´s device
על שם ממציאה כמובן…
זה בעצם סוג של memcpy, שמנסה לשפר את הביצויים על פני לולאה שכל פעם מעתיקה בית יחיד(עוד מהימים שבהם קפיצה בקוד היו פוגעות באופן משמעותי בביצועים). אז מה זה עושה בעצם – מעתיק 8 בתים בבת אחת, כדי להקטין את מספר הקפיצות שצריך לבצע בזמן ההעתקה.השאלה הנשאלת היא מה עושים כשצריך להעתיק אזור בזכרון שגודלו איננו מתחלק ב8, וכאן בעצם הייחוד של הקוד…
הSwitch מבצע קפיצה לאמצע הקוד, בהתאם לשארית Count % 8, ומשם והלאה מבצע לולאת do-while רגילה…כותרת: פרסום של האתר
אני לא יודע מה איתך, אבל לי יצא לראות שלט ענק שמפרסם את התחרות על הבניין של חברת אלדין(רואים אותו מהאיילון).
חוץ מזה, בבי"ס שלי למשל, גם נתלו בכל מקום פוסטרים שמפרסמים את התחרות…כותרת: חבר, אולי תשנה את השם?
אני הייתי מציע לך לשמור את ה eToken, או אפילו להתחיל להשתמש בו:
אתה יכול כבר עכשיו להוריד מפתחות הצפנה/חתימה לטוקן, ואז להשתמש בו לחתימה/הצפנה בטוחה של דואר.
תיכנס ל:
http://www.ealaddin.com/etoken/
בשביל רשימה של כל האפשרויות שמציע לך הeToken, ותוכל להוריד שם גם תוכנות עדכניות בשבילו.(יש מלא, לדוגמא בקרוב יצא להם תוכנה להחלפת ה LOGIN למחשב מסיסמא ל eToken.אגב, הסיסמא שלו היא 1234567890, כמובן שאתה יכול לשנות את זה.
