חידה חביבה בתוכנות

[icebreak]

למביני עניין, הנה חידה חביבה:

כתבו פקודה שמחזירה האם מספר הקלט (INTEGER) הוא חזקה של 2 (יש פתרון לוגוריטמי שהוא פחות יפה, ופתרון הרבה יותר פשוט ויפה במשחקים בינארים).

[Ghosthunter]

לבדוק אם הראשון הוא 0 וכל מה שאחריו הוא 1, עד שמגיעים לרצף אפסים.

למשל:

00011110 חזקה

00000010 חזקה

00100100 לא חזקה

00000001 לא חזקה

לבדוק אם יש אחדים באמצע שיש ביניהם 0 או הראשן לא מתחיל ב0

[icebreak]

דבר ראשון, אתה לא בכיוון, שאלתי חזקה של 2, לא כפולה של 2

11110 = 30 שזה לא חזקה של 2.

דבר שני אמרתי לכתוב פקודה (עדיף בשורה אחת) שעושה את זה, לא שאלתי איך זה אמור להיראות (תחשוב אולי בכיוון של BITWISE OPERATIONS)...

[MB]

הרעיון הוא שצריך להיות רק ביט אחד דולק.

למשל: 01000000 חזקה של 2

לעומת זאת : 01001000 - לא חזקה של 2

חשבתי על משהו לא יעיל במיוחד, אבל הוא צריך לעבוד (לא בדקתי):

for (i=0; (i < sizeof(num)*8) && (((num >> i) & 1) != 1) ; i++);
if ((i < sizeof(num)*8) && ((num >> i) == 1))
	<Power of two>

הרעיון הוא שעוברים על כל המספר ובודקים את הספרה הנוכחית היא 1 ואם המספר שנשאר הוא גם אחד (זאת אומרת שיש רק ביט אחד דולק). ואז המספר הוא חזקה של 2.

[icebreak]

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

[IP]

!(a & (a-1))

אמיתי לחזקה (שלמה) של שתיים ולאפס.

[icebreak]

?!?!?!? קוד C

יעני

int function (int number) { return (some_code());} GOT IT

?

[IP]

int chk_pow_2(int num)

{

return !(num & (num-1));

}

[icebreak]

דבר ראשון סליחה, לא ראיתי שענית בפוסט הקודם שלך (IP)

דבר שני, כל הכבוד

דבר אחרון, צריך גם לבדוק שהמספר הוא לא אפס

int is_pow_log(int v)

{

double a = log10(v)/log10(2);

return (a == round(a)) ? 1 : 0;

}

int is_pow_bit(int v)

{

return !(v & (v - 1)) && v;

}

הפקודה הראשונה גם עושה את זה, אבל בצורה מתמטית הרבה יותר מסובכת.

[Holy]

int is_pow_log(int v)

{

        double a = log10(v)/log10(2);

        return a == (int)(a);

}

יעשה את העבודה

[icebreak]

יעשה את העבודה

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