חידות כי הגיע הזמן

[carlos22]

אולי..לא סגור על מה זה סיבוכיות כ"כ

System.out.println (1/1); for (int i=1; i<=n; i++); for (int j=1; j<i; j++); if !(simplify(i,j); System.out.println(i+"/"+j); public static boolean simplify (int x, int y) {} //returns if 2 numbers //has common divisor

 

[עריסטו]

שתי טעויות יש לך

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

 

[carlos22]

יש רמז ? כיוון ?

 

[עריסטו]

רמז...

אני לא יודע אם זה רמז מספיק רמזי

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

 

[ron369]

נסה אולי לחשוב על שיטה "לסדר" את

האיברים, כך שיתקבלו כל המספרים בתחום המתאים, ממויינים. אחר"כ, להחליט אם מספר באמת בקטע, ואם כבר חזרנו עליו, ממש לא קשה.

 

[carlos22]

כל האיברים בתחום

לא אמור להיות בעיה, אבל אם הם מסודרים בתוך מערך לדוגמא ואחרי זה צריך לרוץ על המערך בשביל לבדוק עבור כל איבר אם הוא שווה לאיבר שכבר הופיע זה לא מעלה את הסיבוכיות בכמה רמות ? (שוב אני לא סגור על סיבוכיות, עוד לא שנה א' אפילו)

 

[ron369]

זה כן. יש שיטה יעילה יותר

 

[carlos22]

תכוון..

לא נראה לי שאני מתקדם לאנשהו מאז הנסיון הראשון

 

[עריסטו]

../images/Emo58.gif פתרון ב - ++C

void f(int n) { int x0 = 0, y0 = 1, x1 = 1, y1 = n, x2, y2, m; cout << x0 << "/" << y0 << x1 << "/" << y1 << endl; while (y1 > 1) { m = (y0 + n) / y1; x2 = m * x1 - x0; y2 = m * y1 - y0; x0 = x1; y0 = y1; x1 = x2; y1 = y2; cout << x1 << "/" << y1 << endl; } }​

 

[עריסטו]

תיקון קטן (שההדפסה תצא כמו שצריך)

void f(int n) { int x0 = 0, y0 = 1, x1 = 1, y1 = n, x2, y2, m; cout << x0 << "/" << y0 << endl << x1 << "/" << y1 << endl; while (y1 > 1) { m = (y0 + n) / y1; x2 = m * x1 - x0; y2 = m * y1 - y0; x0 = x1; y0 = y1; x1 = x2; y1 = y2; cout << x1 << "/" << y1 << endl; } }​

 

[inbal76]

אם לא נתון אם המשקולת השונה

היא כבדה יותר או קלה יותר אז זה בלתי אפשרי.

 

[נופרבלע]

צודקת.

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

 

[inbal76]

במשקל גרמים זה ברור עוד יותר שאין

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

 

[נופרבלע]

תודה רבה לך.

עזרת לי מאוד. =]

 

[bitesizee]

חסר

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

 

[נופרבלע]

ממ תודה.

פתרתי את הבעיה הקודמת,תודה רבה למי שעזר.(ענבל,במיוחד לך). אבל עכשיו יש לי עוד בעיה=\ ישנן 27 משקולות,כולן שוקלות אותו דבר מבלבד אחת מהן.המשקולת השונה כבדה יותר מן השאר.חובה לפתור את הבעיה ב-3 שקילות בלבד. מישהו מוכן לעזור לי? ושוב,תודה לכם.

 

[ahab]

תחשבי על החידה הבאה:

 

[ahab]

תחשבי על החידה הבאה:

יש לך 3 משקולות, אחת כבדה יותר, ומותר לך לבצע שקילה אחת בלבד. זה יעזור לך להגיע לפתרון.

 

[נופרבלע]

חשבתי על זה.

אבל זה עדיין לא נתן לי שום רמז. אני עדיין לא מצליחה בשום דרך:\.

 

[ron369]

לא מצליחה את הרמז,או החידה המקורית?