רוטר - חלוקת עודף, דווקא פשוט.

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חלוקת עודף, דווקא פשוט."

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #7228	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 7228

dryice

13:24 30.10.03

חלוקת עודף, דווקא פשוט.

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

נ.ב
בקרוב קוד C.

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
לא הבנתי את ה''ללא שארית''	E-do	30.10.03 13:38	1
לצורך הפשטות היחידה המינמלית שלנו היא אגורה.	dryice	30.10.03 13:45	2
לא אופטימלי: דוגמא נגדית:	dryice	30.10.03 13:59	3
אומנם לא אופטימלי	liranr	30.10.03 14:22	4
במקרה ראיתי נהג אוטובוס אתמול ונזכרתי.	dryice	30.10.03 14:46	5
אני אודה לך אם תעשה את זה	liranr	30.10.03 14:51	6
לא אופטימלי, אבל גם לא קיים	E-do	30.10.03 15:46	7
בהתחשב בעובדה שאני שאלתי את השאלה המקורית	liranr	30.10.03 16:44	8
האמת היא שבהתחלה הודעתו של dryice קצת	E-do	30.10.03 17:38	9
אבל שוב, גם זה יכול לטעות בגדול	liranr	30.10.03 19:13	10
אבל זה לא המצב הקיים	E-do	30.10.03 20:21	11
משהו שחשבתי אליו...	the_jackass	03.11.03 00:31	12
זה פתרון אקספוננציאלי	dryice	03.11.03 00:41	13
אחי יש כבר קוד ב c אני רוצה לראות איך עושים	TheCoolMan	03.11.03 00:52	14
לא כתבתי כי הבנתי שזה לא פתרון טוב	dryice	03.11.03 01:28	15
רעיון	yoash	09.11.03 22:07	16
גם לא יפתור הבעיה.	dryice	10.11.03 01:41	17
למה לא לעשות לולאה	Feikin	10.11.03 06:52	18
היה לנו כזה תרגיל אבל עם 20 ו50	Jojo X Noah	10.11.03 16:18	19
שנה עברה, ויש לי עדכון	liranr	07.08.04 11:35	20
וואי ... ענתיקה ....	אופירוש	07.08.04 13:32	21
בהתחשב בעובדה שכאמור מדובר ב NP-hard	liranr	07.08.04 14:07	22
להגיד תאמת זה לא כזה קשה	no_angel	08.08.04 17:40	23
לך תדע הכל יכול להיות,	dryice	09.08.04 19:45	24
מה?לא הבנתי מילה ממה שאמרת	no_angel	10.08.04 02:45	25
מה שתיארת נשמע פתרון בזבזני גרידא	dyermaker	10.08.04 04:03	26
התגובה לעיל היא כמובן להודעה מס' 21	dyermaker	10.08.04 04:05	27
הרי אמרתי את זה ...	אופירוש	10.08.04 21:42	28
פשש.. מאמר מבריק	dyermaker	12.08.04 10:57	29
ובקשר לנהג אוטובוס.. אין לו מה לדאוג	dyermaker	12.08.04 11:02	30

E-do
חבר מתאריך 29.10.03
2160 הודעות

13:38 30.10.03

1. לא הבנתי את ה''ללא שארית''
בתגובה להודעה מספר 0

נניח ואני צריך לתת לך עודף של 17.20 ש"ח
הכי אופטימלי יהיה מטבע של 10, מטבע של 5, 2 של שקל, ו-2 של 10 אג'.
ללא שארית, רק 1 מתחלק ב17...

-----------------
בברכה,
e-do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

13:45 30.10.03

2. לצורך הפשטות היחידה המינמלית שלנו היא אגורה.
בתגובה להודעה מספר 1

ואנחנו נעבוד רק בשלמים:
ואז יש לנו סכום של 1720
נרצה להשתמש במטבעות של: 5,10,50,100,500,1000
האלגוריתם שלנו יבדוק מה המטבע הגדול ביותר שהסכום 1720
מתחלק בו, והתשובה תהיה 10.
אז נקצה מטבע אחד של 10 אגרות ונשאר עם 1710
ננסה שוב ושוב נקצה מטבע של 10 אגרות ונשאר עם 1700
כעת המטבע הגדול ביותר שמתחלק ללא שארית הוא 100 נקצה כזה,
נשאר עם 1600
ושוב כנ"ל נשאר עם 1500
כעת הסכום מתחלק ב500 נקצה מטבע של 500 ונשאר עם 1000
נקצה מטבע של 1000 נשאר עם 0 וסיימנו.
והגענו בדיוק לפתרון האופטימלי שאתה הצעת.
סך הכל הקצנו מטבעות: 1000,500,100,100,10,10

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

13:59 30.10.03

3. לא אופטימלי: דוגמא נגדית:
בתגובה להודעה מספר 0

מטבעות בשווי: 9,7,4,1
להגיע לסכום 11.
פתרון אופטימלי: 7+4
האלגוריתם מניב: 9+1+1

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

14:22 30.10.03

4. אומנם לא אופטימלי
בתגובה להודעה מספר 3

ערכתי לאחרונה בתאריך 30.10.03 בשעה 14:30 בברכה, liranr

אבל כמה רחוק ממנו, אתה יכול להעריך?
עריכה:דרך אגב, אני לא חושב שלהסתכל על נהג אוטובוס יעזור לך במשהו, כי למערכת
המטבעות שלנו יש תכונה מיוחדת שהופכת את החישוב לנורא קל.
כל שני מטבעות (או שטרות, בשבילנו זה אותו דבר) שתקח, תגלה שאחד מהם שווה
לכפולה מדוייקת של השני (שטר של 200 הוא בדיוק 4 שטרות של 50, מטבע של
10 שקלים הוא בדיוק 2 מטבעות של 5 שקלים וכך הלאה).
לדעתי (כרגע בלי הוכחה פורמלית), במערכת כזאת האלגוריתם החמדני הפשוט
(קח כל פעם את המטבע הגדול ביותר שנכנס) אמור לעבוד באופן אופטימלי בלי בעיה.
לכן המערכת היא לא אינדיקציה לכלום
עריכה של העריכה:למען האמת שכחתי משטר של 20 שקלים, אז
מה שאמרתי לא ממש מדוייק. בכל זאת יש לי הרגשה שהפיתרון ה"חמדני" יתן במערכת
שלנו תמיד תשובה מדוייקת (אני אשמח אם תמצא לי דוגמא נגדית)

יפה שחודש אחרי שאני התייאשתי מהבעיה שלי אתה עדיין חושב עליה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

14:46 30.10.03

5. במקרה ראיתי נהג אוטובוס אתמול ונזכרתי.
בתגובה להודעה מספר 4

אי אפשר לחסום את השגיאה של האלגוריתם שנתתי לעיל:
דוגמא נוספת:
מטבעות: 900,700,400,1 להגיע לסכום 1100
חבר שלי פה ראה את האשכול וטוען שהוא פותר בN^2
אני אתחקר אותו מאוחר יותר.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

14:51 30.10.03

6. אני אודה לך אם תעשה את זה
בתגובה להודעה מספר 5

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

E-do
חבר מתאריך 29.10.03
2160 הודעות

15:46 30.10.03

7. לא אופטימלי, אבל גם לא קיים
בתגובה להודעה מספר 3

השאלה היא האם אנחנו מנסים לפתור כל מצב תאורטי, או רק מצבים קיימים כלומר מטבעות של 1,5 ו10.
לא סתם החליטו על הערכים הנ"ל, האם יש מצב לא אופטימלי בו האלגוריתם יכשל בהנתן מטבעות אלו?

-----------------
בברכה,
e-do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

16:44 30.10.03

8. בהתחשב בעובדה שאני שאלתי את השאלה המקורית
בתגובה להודעה מספר 7

אני חושב שאני יכול לענות לך.
מה שאני ניסיתי לעשות הוא לקבוע איזו מערכת מטבעות היא אופטימלית (על
סל מחירים כלשהו, לא משנה כרגע) מבין כל המערכות האפשריות (אנחנו מדברים
על סכומים יחסית נמוכים, אז אין כל כך הרבה מערכות שונות אפשריות).
לצורך כך הייתי צריך כמובן לבדוק גם מערכות לא "נוחות", ופה הבעיה.
למען האמת, גם על המערכת שלנו האלגוריתם של dryice לא ממש יעבוד.
זכור שהמערכת שלנו היא 1,5,10,20,50,100,200 ונסה להגיע ל-80. האלגוריתם
של dryice יתן 20+20+20+20, והפיתרון האופטימלי הוא 50+20+10
לעומת זאת, אני די משוכנע שבמערכת שלנו יפעל האלגוריתם ה"חמדני", כלומר
להוציא כל פעם את המטבע הגדול ביותר האפשרי (למרות שלא הוכחתי את זה, זה
רק הרגשה)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

E-do
חבר מתאריך 29.10.03
2160 הודעות

17:38 30.10.03

9. האמת היא שבהתחלה הודעתו של dryice קצת
בתגובה להודעה מספר 8

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

-----------------
בברכה,
e-do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

19:13 30.10.03

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

נניח שהמטבעות שלנו הם 1,30,50 ואנחנו רוצים להגיע ל-60.
הפיתרון האופטימלי הוא 2 מטבעות, אבל "ללכת מהגדול לקטן" יתן פה 11 מטבעות.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

E-do
חבר מתאריך 29.10.03
2160 הודעות

20:21 30.10.03

11. אבל זה לא המצב הקיים
בתגובה להודעה מספר 10

לכן הבדלתי בין כל מצב תאורטי (מטבעות של 7 ו9 !?) לבין המצב הקיים היום (ברוב המקומות בעולם)
ראית פעם מטבע/שטר בערך של 30?

-----------------
בברכה,
e-do

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

the_jackass

00:31 03.11.03

12. משהו שחשבתי אליו...
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 03.11.03 בשעה 00:39 בברכה, the_jackass

יכולים להיות שני פתרונות לבעיה אחת
לדוגמא כדי להגיע ל-11 עם 2,3,9,8,1
גם 2+9 מתאים וגם 3+8 מתאים
עכשיו אני חשבתי על שיטה אחרת, הרבה פחות יעילה, שיכולה להביא מספר פתרונות אופטימליים
זה הולך ככה:
האלגוריתם יריץ את כל האפשרויות הקימות עד שהוא מגיע לסכום המבוקש, ויקבע את מספר המטבעות שהתקבל כמינימלי. (אם הרצף עבר את הסכום המבוקש, עוברים הלאה)
הוא שוב יריץ את כל האפשריות אך ברגע שמספר המטבעות שווה למספר המינימלי, הוא יפסיק את הרצף הספציפי הזה וימשיך לרצף הבא, עד שהוא לא מוצא מספר מינימלי קטן יותר, או שנגמרים הרצפים.
האלגוריתם זוכר את כל הרצפים שמתאים למספר המינימלי.
לדוגמא: (עם המספרים מלמעלה 1,2,3,9,8 והסכום 11)
אם המספר המינימלי נקבע כ-5 לסכום 2+2+2+2+3
אז אם אחרי זה האלגוריתם יגיע לרצף 1+1+1+1+1, הוא לא ימשיך לנסות להגיע ל-11, אלא יעבור לרצף הבא.
אם הוא יגיע לרצף 3+3+3+1+1 אז הוא ישמור אותו כרצף מתקבל (ביחד עם 2+2+2+2+3)
ואם הוא מגיע ל 3+3+3+2 אז המספר המינימלי נקבע כ-4
ומתחילים הכל מהתחלה
אני יודע שיש פה קצת בלגאן אז אני מקווה שהבנתם על מה אני מדבר.
שאלות/הצעות/תיקונים ושאר ירקות יתקבלו בברכה
ד"א
אין לי ידע רב בתיכנות (3 יחידות מחשבים ) ככה שאין לי מושג איך לישים את זה, ואני ישמח אם תגידו לי אם זה בכלל ניתן לישום.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

00:41 03.11.03

13. זה פתרון אקספוננציאלי
בתגובה להודעה מספר 12

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheCoolMan

00:52 03.11.03

14. אחי יש כבר קוד ב c אני רוצה לראות איך עושים
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 03.11.03 בשעה 00:53 בברכה, TheCoolMan

את זה לא הצלחתי לעשות...
בתודה מראש

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

01:28 03.11.03

15. לא כתבתי כי הבנתי שזה לא פתרון טוב
בתגובה להודעה מספר 14

אין לו יתרונות מהותיים על האלגוריתם החמדני הנאיבי ביותר,
לממש בC זה לא בעיה גדולה, אבל זה לא מעניין.
במקרה הדוגמא שלי לאיך לגרום לאלגוריתם החמדני הנאיבי
לפשל בגדול היה להגיע ל198 עם 100,99 ו1. ושם במקרה
האלגוריתם החמדני מפשל ומה שהצעתי לעיל עובד,
אבל זה לא הכלל השולט, ובסופו של דבר לא הוצע פה פתרון של
ממש.
אם בכל זאת אתה רוצה לממש בC אז זה דיי פשוט.
תקלוט לתוך מערך את גדלי המטבעות החוקיים, או שתדרוש
שהקלט יהיה ממוין או שתמיין אחר-כך.
תכין פונקציית עזר שרצה על המערך מגדול לקטן ומחזירה
את הערך הראשון שמחלק ללא שארית מספר נתון(הפרמטר של הפונקציה)
אז בלולאה אתה מחסיר את תוצאת הפונקציה מהסכום הנותר
עד שנשאר אפס. אבל כאמור זה לא פתרון.

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

yoash

22:07 09.11.03

16. רעיון
בתגובה להודעה מספר 15

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

01:41 10.11.03

17. גם לא יפתור הבעיה.
בתגובה להודעה מספר 16

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Feikin

06:52 10.11.03

18. למה לא לעשות לולאה
בתגובה להודעה מספר 17

שכל פעם שמספר שיורד ממנה הוא משתנה , שמשתנה ברגע שהוא גדול מהסכום ושהערך הראשוני שלו הוא הגדול ביותר? מקווה שאני מובן :|

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Jojo X Noah

16:18 10.11.03

19. היה לנו כזה תרגיל אבל עם 20 ו50
בתגובה להודעה מספר 0

מה שאני עשיתי התחלתי לא עם 50 הגדול אלא עם 20
ואז בדקתי אם אני יכול להמיר את זה ל50

אני עוד מעט אבנה משהו בסיסי בפסקל ואעלה...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

11:35 07.08.04

20. שנה עברה, ויש לי עדכון
בתגובה להודעה מספר 0

נראה אולי קצת חסר טעם להקפיץ הודעה מלפני שנה, אבל יש לי עדכון שאולי יעניין מישהו:
ממאמר שנתקלתי בו במקרה, עולה כי הבעיה (הידועה יותר בתור change making problem) היא אכן NP-hard, כמו ש dryice חשש במקור.
אבל זה לא הנושא של ההודעה הזאת, אלא בעיה אחרת:
כזכור, ה"פיתרון החמדני" משמעו לקחת תמיד את המטבע הגדול ביותר האפשרי.
אפשר לשאול בהינתן מערכת מטבעות C וערך x, האם הפיתרון החמדני ליצוג x הוא גם האופטימלי?
כמו כן, אפשר לשאול האם זה נכון למערכת מטבעות C עבור כל ערך של x.

לכאורה, הבעיה השנייה נראית קשה בהרבה מהראשונה - קשה אפילו לראות למה יש לה אלגוריתם שעובד בזמן סופי, כי יש אינסוף ערכים ל-x.
למעשה, הבעיה הראשונה היא בעיית NP-hard, בעוד שהבעיה השנייה פתירה ב (O(N^3, כאשר N הוא מספר המטבעות.
נשמע מוזר, אבל הנה תיאור של האלגוריתם (מאמר מתמטי - לא טריוויאלי לקריאה): http://tinyurl.com/69fax

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

אופירוש

13:32 07.08.04

21. וואי ... ענתיקה ....
בתגובה להודעה מספר 20

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

14:07 07.08.04

22. בהתחשב בעובדה שכאמור מדובר ב NP-hard
בתגובה להודעה מספר 21

וזאת עובדה שנתקלתי בה ביותר ממקור אחד, הטענה הזאת נראית לא סבירה...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

no_angel
חבר מתאריך 20.3.02
4989 הודעות

17:40 08.08.04

23. להגיד תאמת זה לא כזה קשה
בתגובה להודעה מספר 22

כלומר התאוריה של כותב ההודעה מן הסתם הכי הגיונית לא?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

19:45 09.08.04

24. לך תדע הכל יכול להיות,
בתגובה להודעה מספר 22

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

no_angel
חבר מתאריך 20.3.02
4989 הודעות

02:45 10.08.04

25. מה?לא הבנתי מילה ממה שאמרת
בתגובה להודעה מספר 24

כלומר זה הVertexCover?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dyermaker
חבר מתאריך 4.2.03
1644 הודעות

04:03 10.08.04

26. מה שתיארת נשמע פתרון בזבזני גרידא
בתגובה להודעה מספר 21

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

בקיצור התכנית שתיארת נשמעת יצירתית בכיוון השלילי...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dyermaker
חבר מתאריך 4.2.03
1644 הודעות

04:05 10.08.04

27. התגובה לעיל היא כמובן להודעה מס' 21
בתגובה להודעה מספר 26

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

אופירוש

21:42 10.08.04

28. הרי אמרתי את זה ...
בתגובה להודעה מספר 26

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dyermaker
חבר מתאריך 4.2.03
1644 הודעות

10:57 12.08.04

29. פשש.. מאמר מבריק
בתגובה להודעה מספר 20

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dyermaker
חבר מתאריך 4.2.03
1644 הודעות

11:02 12.08.04

30. ובקשר לנהג אוטובוס.. אין לו מה לדאוג
בתגובה להודעה מספר 29

אם אין לי באג בתכנית אז מערכת המטבעות/שטרות שלנו בישראל מאפשרת לו לפתור את הבעיה בחמדנות :-)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד