חידה קשה

[rukori]

אני מחפש אלגוריתם שעונה לחידה הבאה:

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

דוגמא:
N=1 D=4
answer= 0.25

N=5 D=6
answer= 0.8
(3)

N=1 D=7
answer= 0
(142857)

תודה מראש!

[CodeGuru]

אכן שאלה נחמדה.
אפשר להוסיף לה שאלה מתמטית – הוכח שהאלגוריתם תמיד יעצור.

[Armageddon90]

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

[Armageddon90]

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

[CodeGuru]

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

[Armageddon90]

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

[מאת]

תגובות