פתרון החידה של התחרות השניה

עמוד

ברוכים הבאים לאתר תחרויות קודגורו! פורומים חידות פתרון החידה של התחרות השניה

מוצגות 15 תגובות – 1 עד 15 (מתוך 16 סה״כ)
  • מאת
    תגובות
  • #80146
    אור
    משתתף

    כותרת: תוספת קטנה ששכחתי… הקוד…
    ai(p(63,X,Y),FinalBoard,FinalBoard):-
    last(FinalBoard,p(0,NX,NY)),
    (
    (abs(NX-X) =:= 3,abs(NY-Y)=:=4)
    ;
    (abs(NX-X) =:= 4,abs(NY-Y)=:=3)
    ;
    (abs(NX-X) =:= 5,NY=:=Y)
    ;
    (abs(NY-Y) =:= 5,NX=:=X)
    ).
    ai(p(Num,X,Y),Board,FinalBoard):-
    Num<63,
    PNum is Num+1,
    (
    ( (X=<img src="smileys/heart.gif" width="" height="" alt="<3" title=",NX is X+5,NY is Y) ; (X>=6, NX is X-5,NY is Y) )
    ;
    ( (Y=<img src="smileys/heart.gif" width="" height="" alt="<3" title=",NY is Y+5,NX is X) ; (Y>=6,NY is Y-5,NX is X) )
    ;
    ( (X==4, NX is X-3) , (Y==5, NY is Y-4))
    ;
    ( (X==5,NX is X-4) , (Y==4, NY is Y-3))
    ),
    not(member(p(_,NX,NY),Board)),
    ai(p(PNum,NX,NY),[p(PNum,NX,NY)|Board],FinalBoard).

    כדי לראות בצורה טובה יש להעביר למצב LTR

    #77739
    אור
    משתתף

    למי שלא היה, אחרי התחרות הרגילה הייתה תחרות נוספת בקבוצות.
    בתחרות הזאת המטרה הייתה להגיע למצב בו המספרים מ0 עד 63 ממלאים לוח 8X8 כך שהמרחק בין כל מספר לעוקב ולקודם שלו הוא 5.
    לדוגמא אם 0 במקום 1,1 אז המספר אחד יכול להיות ב 6,1 או 1,6 או 4,5 או 5,4.
    (שתי הדוגמאות האחרונות במרחק חמש לפי שלשה פיתגורית 3 4 5)

    בתחרות הקבוצה שלי לא הצליחה להגיע למקסימום של 64 נקודות(כל צמד מספרים עוקבים במרחק חמש הוא נקודה), למרות שניסינו גם ע"י ניסיונות וגם ע"י כתיבת תוכנה.(אחת בפסקל ואחת בפרולוג)

    במהלך התחרות התוכנה בפרולוג שכתבתי די תקעה את המחשב…
    כשחזרתי הבייתה כבר הבנתי מה הייתה הבעיה בתוכנית, ועכשיו כבר יש לי פתרון לחידה:

    | 51 | 34 | 1 | 16 | 37 | 54 | 49 | 0 |
    | 32 | 19 | 40 | 57 | 4 | 31 | 20 | 39 |
    | 45 | 6 | 13 | 28 | 23 | 60 | 7 | 14 |
    | 36 | 25 | 48 | 63 | 10 | 35 | 26 | 47 |
    | 17 | 42 | 55 | 50 | 33 | 18 | 41 | 56 |
    | 52 | 59 | 2 | 15 | 38 | 53 | 58 | 3 |
    | 29 | 22 | 61 | 46 | 5 | 30 | 21 | 62 |
    | 44 | 9 | 12 | 27 | 24 | 43 | 8 | 11 |

    #80149
    אור
    משתתף

    כותרת: שחכתי להוסיף… זה כמובן לא הפיתרון היחיד…

    #80151
    אור
    משתתף

    כותרת: רעיון
    אני עדיין לא יודע איך אפשר ללא מחשב אבל שמתי לב לכמה דברים שאולי יובילו לתשובה.
    אם מסתכלים על המספרים שנמצאים בקצוות אז סיפרת היחידות שלהן בדר"כ(אם זה היה תמיד אולי כבר היה לי כלל לעקוב אחריו)
    מתאימה לסיפרת היחידות בקצה לידה…
    לדוגמא:
    39/49
    14/54
    37/47
    16/56
    וכו´..

    עוד דבר שמתי לב כתוצאה מהראשון שאולי יש איזהשהו עיניין של סכומים או הפרשים בכל אלכסון…
    מאחר ויש בהתחלה סידרה של הפרשים שחוזרת על עצמה…
    10
    40
    10
    40

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

    #80153
    CodeGuru
    מנהל בפורום

    כותרת: יפה! אבל אפשר לפתור גם בלי מחשב
    תוכנית ה-פרולוג קצרה ויעילה מוכיחה ששפות
    B&D (למי שהיה בהרצאת ד"ר ישי פלדמן)
    אכן מתאימות מאוד לייעודן.

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

    אפשר לפתור את החידה גם בלי מחשב, ובלי יותר מדי ניסיונות (על גב מעטפה).

    יש לכם רעיונות איך?

    חג שמח!

    #80155
    מתן
    משתתף

    כותרת: תוכל להסביר את הקוד?

    #80159
    צבי
    משתתף

    כותרת: מצאתי את החידה ופתרונה ברשת

    #80160
    אור
    משתתף

    כותרת: אפשר הסבר לקוד הC?
    מאחר ואני לא מבין יותר מדי בC… ועוד יותר אני לא מכיר את כל הקיצורים שיש בC…

    מהמעט שאני יודע אתה יכול להסביר למה בלולאת הfor אין הגדלה של i ואין הגבלה לן?
    בנוסף למה למשפט התנאי שבלולאה אין חלק של then …
    (אני רק מניח שאולי זה איזה שהוא קיצור שעוצר את הלולאה…)
    עוד דבר… אני לא רואה איך במקרה שאין צעד אפשרי תהיה חזרה אחורה ובחירת צעד אחר…

    #80161
    אור
    משתתף

    כותרת: הסבר לקוד
    אני אתחיל עם המתארים של החוק..
    ai(p(Num,X,Y),Board,FinalBoard).
    p(Num,X,Y) הוא האיבר האחרון שהכנסתי לרשימה שמתארת את הלוח…
    כאשר Num הוא המשפר ויש לו את הקורדינטות X ו Y.
    (כעיקרון אני לא באמת צריך 3 מתארים אבל בזמן הכתיבה זה היה לי יותר נוח מאשר לפצל את הרשימה בראש החוק).
    Board הוא הלוח אשר בנוי מרשימה של איבר p(Num,X,Y)…
    בקריאה הראשונה לחוק צריך לקרוא לו עם המספר 0 ואני בחרתי לצורך הנוחות תמיד למקם את 0 במשבצת 1,1. לכן הקריאה לחוק תיהיה ככה:
    a(p(0,1,1),[p(0,1,1)],FinalBoard).
    בגוף החוק אני פשוט מוודא שהמספר קטן מ 63 ואז שם ב PNum את המספר העוקב הבא.
    אז אני פשוט הבעתי את כל אפשרויות התזוזה בפרולוג כאשר הן מפרדות ב; על מנת שבמקרה ומתישהו והחוק נכשל במציאת מקום למספר כלשהו אז בחזרה תבחר אפשרות אחרת.
    אחרי שנבחרת איזו שהיא משבצת, יש בדיקה שהמשבצת לא תפוסה:
    not(member(p(_,X,Y),Board)
    כלומר שלא קיים איבר ברשימה בעל מיקום X ו Y שתואם את ה X ו Y החדשים.
    לאחר מכן אני פשוט מבצע קריאה רקורסיבית לחוק כאשר אני מוסיף לרשימה את המספר החדש עם המיקום שלו.
    כלל העצירה של הרקורסיה הוא אחרי שממקימים את המספר 63 ואז נעשית בדיקה שהוא אכן במרחק חמש מ 0…
    (למרות שיש לי הרגשה שאולי אם כבר מצליחים למקם את 63 ביחס ל62 אז הוא גם חייב להיות במרחק חמש מ 0.

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

    מי שמעניין אותו פרולוג, יכול להיכנס לקישור שהבאתי…
    זה ספר אלקטרוני מאוד טוב שמסביר לעומק את פרולוג.
    ואם מישהו מחפש מפענח(אני לא ממש יודע מה המילה המוסכמת ל interperter) לפרולוג, יש אחד טוב מאוד והוא אף בקוד פתוח.
    http://www.swi-prolog.org

    #80162
    Olimpus team
    משתתף

    כותרת: והנה פתרון ב c

    enum{W=8,H=8,N=12};

    int solve(int m[W][H],int x,int y,int n)
    {
    static int rel_moves[N][2]={
    {-5,0},{5,0},{0,-5},{0,5},
    {-3,4},{3,4},{3,-4},{-3,-4},
    {-4,3},{4,3},{4,-3},{-4,-3}
    };
    if(n>=W*H) return 1;
    for(int i=0;i<N;i++)
    {
    int cx=x+rel_moves[0];
    int cy=y+rel_moves
    [1];
    if((cx>=0)&&(cx=0)&&(cy<=H)&&(m[cx][cy]<0))
    {
    m[cx][cy]=n;
    if( solve(m,cx,cy,n+1) ) return 1;
    else m[cx][cy]=-1;
    }
    }
    return 0;
    }

    #80163
    Olimpus team
    משתתף

    כותרת: העלתי. ראה קישור

    #80164
    אור
    משתתף

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

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

    #80165
    Olimpus team
    משתתף

    כותרת: זו שגיאה של הפורום(: יש הגדלה ויש הגבלה. מתוקן:

    int solve(int m[W][H],int x,int y,int n)
    {
    static int rel_moves[N][2]={
    {-5,0},{5,0},{0,-5},{0,5},
    {-3,4},{3,4},{3,-4},{-3,-4},
    {-4,3},{4,3},{4,-3},{-4,-3}
    };
    if(n>=W*H) return 1;
    for(int i=0;i<N;i++)
    {
    int cx=x+rel_moves[0];
    int cy=y+rel_moves
    [1];
    if((cx>=0)&&(cx=0)&&(cy<=H)&&(m[cx][cy]<0))
    {
    m[cx][cy]=n;
    if( solve(m,cx,cy,n+1) ) return 1;
    else m[cx][cy]=-1;
    }
    }
    return 0;
    }

    #80166
    Olimpus team
    משתתף

    כותרת: LOL הפורום מסרב לכתוב (++i<N; i

    #80167
    אור
    משתתף

    כותרת: אולי תעלה את הקובץ לאיזה שהוא שרת?

מוצגות 15 תגובות – 1 עד 15 (מתוך 16 סה״כ)
  • יש להתחבר למערכת על מנת להגיב.