רוטר - הפיכת שבר עשרוני לשבר רגיל מצומצם בשפת C

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

"הפיכת שבר עשרוני לשבר רגיל מצומצם בשפת C"

גירסת הדפסה

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

אשכול מספר 6351

liranh

חבר מתאריך 16.6.09
4157 הודעות, 1 פידבק

14:29 18.06.03

הפיכת שבר עשרוני לשבר רגיל מצומצם בשפת C

אני באמצע תוכנית בשפת C, ואני צריך דרך להפוך שבר עשרוני לשבר רגיל מצומצם. לדוגמא:

0.23=7/50
למישהו יש רעיון איך לעשות את זה?
אני צריך שיהיה לי את המונה במשתנה אחד, ואת המכנה במשתנה שני.

תודה מראש

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
זה טיפה בעייתי שכן,	dryice	18.06.03 14:39	1
מכתב	liranh	18.06.03 14:49	2
רעיון לפתרון	nevola	18.06.03 15:49	3
את זה אפשר לעשות הרבה יותר מהר.	dryice	18.06.03 16:14	4
אח שלי תודה רבה !	liranh	18.06.03 22:04	15
או שאני לא הבנתי או שהדוגמא לא טובה	liranr	18.06.03 16:25	5
צודק סליחה	liranh	18.06.03 21:01	11
פתרון אמיתי מלא	nevola	18.06.03 16:49	6
צריך לדאוג לשים slack בסוף	dryice	18.06.03 17:24	7
מימוש לדוגמא:	dryice	18.06.03 20:30	9
שאלה:	Dudenland	18.06.03 19:54	8
יש לך הוכחה שהוא עוצר תמיד?	dryice	18.06.03 20:34	10
בטח שהוא עוצר !	Dudenland	18.06.03 22:03	14
תודה רבה אחי!	liranh	18.06.03 21:04	12
יש בעיה מהותית מבחינה מתמטית.	שמש העמים	04.08.03 01:15	24
תמיד עובדים עם מרווח נשימה	dryice	04.08.03 02:10	25
שאלה לכולם:	liranr	18.06.03 21:40	13
עבור הקלט 0.3333	dryice	19.06.03 00:37	16
אתה רוצה תשובה 1/3?	liranr	19.06.03 09:50	17
Dryce, 0.3333	Vidi	27.06.03 19:11	19
אני לא מסכים.	dryice	27.06.03 20:00	20
אתה צריך לבנות יחידת ספריה לדבר הזה...	שאשא	27.06.03 15:36	18
יש לי רעיון:	yoash	01.07.03 13:35	21
תודה	moko	06.07.03 08:10	22
אין בעד מה אבל על מה ?	yoash	06.07.03 13:01	23

dryice

14:39 18.06.03

1. זה טיפה בעייתי שכן,
בתגובה להודעה מספר 0

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

DRYICE

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

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

liranh

חבר מתאריך 16.6.09
4157 הודעות, 1 פידבק

14:49 18.06.03

2. מכתב
בתגובה להודעה מספר 1

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

תודה רבה אחי

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

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

nevola

15:49 18.06.03

3. רעיון לפתרון
בתגובה להודעה מספר 2

תתחיל מ - 1/2, תכפיל מונה ומכנה ב- 2
אם זה גדול מהדרוש - תוריד אחד מהמונה, אם זה קטן - תוסיף אחד.
תחזור בלולאה עד לדיוק הרצוי, או כמה איטרציות שתרצה.
בסוף תצמצם את השבר.
לדוגמא שלך -
1/2 -> 2/4 גדול מ- 0.23 אז אני מוריד מהמונה ונשאר עם 1/4
1/4 -> 2/8 גדול מ- 0.23 אז אני מוריד מהמונה ונשאר עם 1/8
1/8 -> 2/16 קטן מ- 0.23 אז אני מוסיף למונה ונשאר עם 3/16
3/16 -> 6/32 קטן מ- 0.23 אז אני מוסיף למונה ונשאר עם 7/32
7/32 -> 14/64 קטן מ- 0.23 אז אני מוסיף למונה ונשאר עם 15/64
15/64 -> 30/128 גדול מ- 0.23 אז אני מוריד מהמונה ונשאר עם 29/128
29/128 -> 58/256 קטן מ- 0.23 אז אני מוסיף למונה ונשאר עם 59/256

59/256 = 0.2304

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

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

dryice

16:14 18.06.03

4. את זה אפשר לעשות הרבה יותר מהר.
בתגובה להודעה מספר 3

הרי המחשב כשהוא שומר מספר במשתנה נקודה צפה, הוא למעשה
שומר שני מספרים שלמים(עם סימן) כך שערך המשתנה הוא:
Mantisa*2^exp
למצוא את הMantisa והexponent זה מאוד פשוט, אבל כאמור
זה יניב תוצאות עם מכנה מאוד מאוד גדול.
אם אני רוצה לקבל עבור 0.2 את הפתרון 1/5 אני חייב שיטה אחרת.
אני אומר ניתן פונקציית מחיר לשבר נתון, כך שניתן מחיר גבוהה
לשבר ששונה בהרבה מהמספר המבוקש, וכן ניתן גם מחיר גבוהה
ככל שהמכנה של המספר גדול יותר. ואז נריץ איזה שהוא חיפוש
היוריסטי, בשאיפה למזער את פונקציית המחיר.
אם אנו מחפשים מספר F והשבר שאנו בודקים הוא M/N פונקציית
המחיר עשויה להיות מהצורה:

(M/N - F)^a + c*(N^b)
כאשר a,b,c פרמטרים קבועים כלשהם, (צריך לשחק קצת בשביל
לקבל תוצאות טובות)

DRYICE

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

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

liranh

חבר מתאריך 16.6.09
4157 הודעות, 1 פידבק

22:04 18.06.03

15. אח שלי תודה רבה !
בתגובה להודעה מספר 3

עבר עריכה לאחרונה בתאריך 18.06.03 בשעה 22:04

התבססתי על התוכנית שלך בשביל משהו אחר שרציתי לעשות!

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

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

liranr

16:25 18.06.03

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

0.23 זה ממש לא 7/50. 7/50 יוצא 0.14.

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

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

liranh

חבר מתאריך 16.6.09
4157 הודעות, 1 פידבק

21:01 18.06.03

11. צודק סליחה
בתגובה להודעה מספר 5

התכוונתי לכתוב 0.14 = 7/50

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

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

nevola

16:49 18.06.03

6. פתרון אמיתי מלא
בתגובה להודעה מספר 0

בהינתן מספר עשרוני כלשהו - 0.23
נסמן -
X1 = 0.23
X2 = 1/0.23 = 4.3478
X3 = 1/0.3478 = 2.875
X4 = 1/0.875 = 1.142857
X5 = 1/0.14285 = 7
זה הסוף כי הגענו למספר שלם
והתשובה היא :
מונה - כפל כל האיקסים
מכנה - מונה *( 1 חלקי X1)
זה ייתן פתרון נכון מלא ומדוייק. יש לי גם הוכחה אם מישהו מבקש.

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

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

dryice

17:24 18.06.03

7. צריך לדאוג לשים slack בסוף
בתגובה להודעה מספר 6

בבדיקה האם המספר שלם, אבל כן העסק נראה בחטף נכון.

DRYICE

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

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

dryice

20:30 18.06.03

9. מימוש לדוגמא:
בתגובה להודעה מספר 7

שרבטתי את האלגוריתם המתואר לעיל בC.
לגודל EPSILON שמגדיר מה נחשב שלם, יש השפעה ממש קריטית.
אם אני שם EPSILON קטן מידי, אז האלגוריתם נכשל בענק
כשנותנים לו קלט לא טריוויאלי, או שיחזיר זבל, או שבתם יכנס
לרקורסיה אינסופית.
http://rotter.net/User_files/nor/3ef0a19b35c34cfc.txt
DRYICE

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

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

Dudenland

19:54 18.06.03

8. שאלה:
בתגובה להודעה מספר 6

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

Dudenland

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

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

dryice

20:34 18.06.03

10. יש לך הוכחה שהוא עוצר תמיד?
בתגובה להודעה מספר 6

ואם כן מתי הוא עוצר?
לראות שהפתרון נכון כשהוא עוצר, זה פשוט.
לראות שהוא עוצר, זה עניין אחר, וכמובן מתי הוא עוצר.
האם אפשר לטעון משהוא על סיבוכיות?

DRYICE

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

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

Dudenland

22:03 18.06.03

14. בטח שהוא עוצר !
בתגובה להודעה מספר 10

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

Dudenland

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

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

liranh

חבר מתאריך 16.6.09
4157 הודעות, 1 פידבק

21:04 18.06.03

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

עבר עריכה לאחרונה בתאריך 18.06.03 בשעה 21:04

אם להגיד את האמת, לא הבנתי כל כך את הדרך שלך, אולי אני לא מכיר את השיטה הזאת, אבל אני אשתמש בה בכ"ז, ואנסה להבין תוך כדי

תודה רבה ל-dryice שמימש את הרעיון ולכל מי שניסה לעזור!
אתם גדולים!

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

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

שמש העמים

01:15 04.08.03

24. יש בעיה מהותית מבחינה מתמטית.
בתגובה להודעה מספר 6

אם זה מספר רציונאלי - כלומר עם מספר מדוייק של ספרות אחרי הנקודה - סבבה, אם אין - זה מספר אי-רציונאלי ואין אפשרות. כי עם כל הכבוד
3*0.33 זה לא 1 וגם 3*0.33333333333333333333333333333333333333333333 זה לא 1. זה מספר שהוא מאוד מאוד מאוד מאוד מאוד קרוב ל-1 ואנחנו מרשים לעצמנו לעגל אותו ל-1. גם שורש שתיים זה לא מספר שניתן להציג כשבר רגיל.

אז הכל מסתבך... בהצלחה

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

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

dryice

02:10 04.08.03

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

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

DRYICE

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

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

liranr

21:40 18.06.03

13. שאלה לכולם:
בתגובה להודעה מספר 0

אולי אני ישמע כמו טיפש, אבל מה רע בפתרון ה"טריויאלי"?
לבדוק כמה ספרות יש למספר אחרי הנקודה (נגיד a),
להכפיל אותו ב-10 עד שהוא שלם (שוב צריך להגדיר איזשהו EPSILON בשביל
לקבוע מה זה שלם), נגיד שהמספר השלם הוא b,
ואז פשוט לצמצם את השבר b/10^a? לי נראה כאילו זה יעבוד

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

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

dryice

00:37 19.06.03

16. עבור הקלט 0.3333
בתגובה להודעה מספר 13

הפתרון שלך יחזיר 3333/10000
ואני רוצה תשובה 1/3

DRYICE

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

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

liranr

09:50 19.06.03

17. אתה רוצה תשובה 1/3?
בתגובה להודעה מספר 16

השאלה דיברה על מספרים עשרוניים סופיים שניתן להכניס במדוייק
למשתנה float (בכפוף כמובן למגבלות הייצוג).

אבל אני מסכים כמובן שהפתרון שלי לא לוקח מצבים כאלה בחשבון

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

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

Vidi
חבר מתאריך 1.10.17
591 הודעות

19:11 27.06.03

19. Dryce, 0.3333
בתגובה להודעה מספר 16

לא צריך להחזיר 1/3 :\ שום דבר לא אמור להחזיר 1/3!
כי הרי אי אפשר לייצג שליש במספרים עשרוניים :\

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

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

dryice

20:00 27.06.03

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

כשאני אבקש מבן אדם להפוך 0.3333 לשבר פשוט,
סביר שהתשובה שאקבל היא 1/3
אם אבקש מאדם להפוך 1/3 למספר עשרוני, אקבל איזו שהיא
תשובה בדיוק סופי.
כשאני רוצה להפוך את התהליך יש אי אלו inhernt ambiguities
ואילו בכל זאת אני רוצה לנחש למה התכוון המשורר.
אני חושב שהתשובה 1/3 הרבה יותר מוצלחת מהתשובה 3333/10000

DRYICE

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

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

שאשא

15:36 27.06.03

18. אתה צריך לבנות יחידת ספריה לדבר הזה...
בתגובה להודעה מספר 0

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

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

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

yoash

13:35 01.07.03

21. יש לי רעיון:
בתגובה להודעה מספר 0

עבר עריכה לאחרונה בתאריך 01.07.03 בשעה 13:44

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

typedef struct{
int a,b;
}shever;

A = שבר עשרוני
B = 10 ^ מספר הספרות אחרי הנקודה
C = הספרות שאחרי הנקודה בשבר העשרוני
toll = אחוז הדיוק המתבקש
Array1 = מערך של המספרים הראשוניים בסופו קיים 0
shever func(shever a)
{
int i=0;
while(Array1{i})
{
if(abs(B%Array{i}) < toll && abs(C%Array{i}) < toll))
{
a.a = B/Array{i};
a.b = C/Array{i};
return func(a);
}
i++;
}
return a;
}

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

במחשבה שניה מספיק לחלק כל שבר בחמש ובעשר כי המכנה מתחלק רק ב5 ו10

נ.ב.
צריך להחליף את הסוגריים המסולסלות בפניה למערך בסוגריים מרובעות

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

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

moko
חבר מתאריך 25.5.02
355 הודעות

08:10 06.07.03

22. תודה
בתגובה להודעה מספר 0

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

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

yoash

13:01 06.07.03

23. אין בעד מה אבל על מה ?
בתגובה להודעה מספר 22

ראיתי שהגבת לשתי תגובות שלי במילה תודה.
אבל אתה יכול לפרט בבקשה ?

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

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