פורסם 2004 בספטמבר 721 שנים אתה יכול לפתור את השאלה הזאת בצורה הרבה יותר חכמה...מבחינה מתמטית מספיק לבדוק אם יש למספר מחלקים רק עד השורש הטבעי של המספר (מעוגל כלפי מטה).כלומר להריץ לולאה מ20 עד 700 כאשר עבור כל מספר אתה בודק אם הוא מתחלק ב2 עד השורש הטבעי של המספר.אם אתה מוצא כי בחלוקה אין שארית, אזי אתה משנה את דגל הלולאה ולא מספיס את המספר, כי איננו ראשוני...להלן הקוד הרצוי:#include <stdio.h>#include <conio.h>#include <math.h>void main (){ int rishoni,root,i,j; clrscr(); for (j=20;j<=700;j++) { root=sqrt(j);//the natural square root i=2; rishoni=1;//the flag while (i<=root && rishoni==1) { if (j%i==0) rishoni=0;//the number isn't rishoni i++; } if (rishoni==1)//if no number was divided completely printf("the number %d is rishoni.\n",j); }}
פורסם 2004 בספטמבר 721 שנים vega הקוד שלו לא עובד כי ב-for עושים ; ולא ,A.S.A.P - חישוב שורש די יקר (בעיקרון כל פעולה על מספרים עם נקודה צפה די יקרה), לדעתי עדיף לבדוק עד המספר חלקי 2 בשביל לקבל ביצועים מקסימליים.
פורסם 2004 בספטמבר 721 שנים לפי דעתי מספיק לבדוק חלוקה בכל המספרים הראשוניים שבאו לפניו וכל פעם שאתה מוצא מספר ראשוני אתה מוסיף אותו למאגראין לי ממש כוח להסביר אבל נסו להביןטוב נו ניתן כמה דוגמאות2 ראשוני3 לא מתחלק ב2 ולכן ראשוני4 מתחלק ב2= לא ראשוני5 לא מתחלק לא ב3 ולא ב 2 = ראשוני6 מתחלק ב2 = ראשוני7 לא מתחלק באף אחד מהמספרים הראשוניים שלהלן(2,3,5) ולכן ראשוניוכך הלאהזה בעצם מתבסס על זה שכל מיספר לא ראשוני חייב להכיל בתוכו גורם חלוקה ראשוניאם מצאנו את גורם החלוקה הזה המספר הוא לא ראשוניאם לא מצאנו אז המספר ראשוני
פורסם 2004 בספטמבר 721 שנים A.S.A.P - חישוב שורש די יקר (בעיקרון כל פעולה על מספרים עם נקודה צפה די יקרה), לדעתי עדיף לבדוק עד המספר חלקי 2 בשביל לקבל ביצועים מקסימליים. מבחינת ביצועים "נטו" של המחשב עדיף לחפש עד מחצית המספר,אבל מבחינה רעיונית תוכנית שבודקת עד שורש המספר הרבה יותר "חכמה" ומראה על פיתוח אלגוריתם נכון ויעיל. לפי דעתי מספיק לבדוק חלוקה בכל המספרים הראשוניים שבאו לפניו וכל פעם שאתה מוצא מספר ראשוני אתה מוסיף אותו למאגר אני חושב ששיטה זו תעבוד, אבל כדי לבצע את התהליך הזה הוא צריך לשמור מערך שלם של מספרים שלמים, ובנוסף על כך גודלו אינו ידוע מראש, כך שיהיו תאי זיכרון מבוזבזים.מבחינת זמן ריצה וחיסכון בזיכרון הכי יעיל לבדוק עד מחצית המספר.
פורסם 2004 בספטמבר 721 שנים ניראה לי ששלי יותר יעילאין טעם לדוגמא לבדוק חלוקה ב4 אם כבר מצאנו שהמספר לא מתחלק ב2כמובן בתוספת בדיקה עד (חצי המספר - 1) כי אם המספר מתחלק במחציתו אזי הוא בהכרח מתחלק ב2 ואת זה כבר בדקנואתם יודעים מה..במספרים יותר גדולים מ2 אפילו אפשר עד פחות מ(חצי המספר - 1) אבל צריך קצת יותר להעמיק בזה בשביל להבין את השיטה
פורסם 2004 בספטמבר 721 שנים אני חושב ששיטה זו תעבוד, אבל כדי לבצע את התהליך הזה הוא צריך לשמור מערך שלם של מספרים שלמים, ובנוסף על כך גודלו אינו ידוע מראש, כך שיהיו תאי זיכרון מבוזבזים.מבחינת זמן ריצה וחיסכון בזיכרון הכי יעיל לבדוק עד מחצית המספר.זה גם בזבזנילמה לבדוק חלוקה בכל המספרים הזוגיים עד חצי המספר אם ידוע שהוא לא מתחלק ב2.?זה בזבזני מעוד סיבהתחשוב שניה על המספר 200 אבל בוא נלך אחורניתנבדוק שהוא מתחלק ב100 וואלה אנחנו שמחיםעכשיו בלי לנסות לחשב תגיד לי אם אני באמת הייתי צריך לבדוק את החלוקה של 200 ב 99 או לחילופין ב 98אני לא יודע מה האלגוריתם הכי טוב אבל אני בטוח ב100 אחוז שזה לא אחד מאלה אבל אם הייתי רוצה לעשות על זה עבודה הייתי מעמיק הרבה יותר בנושא מבחינה מתמטית
פורסם 2004 בספטמבר 721 שנים אתה צודק בהחלט!לפי השיטה של בדיקה עד מחצית המספר סורקים בשיטה איטרטיבית (לולאה) את כל המספרים מ2 עד מחצית המספר,וכאשר מגלים התחלקות מפסיקים את הבדיקה!כלומר המספר 200 מתחלק ב2 ואחרי בדיקה אחת בלבד הפסקנו לבדוק.אבל במקרה בו המספר הוא אכן ראשוני המצס שונה לחלוטין - כאן יכול להיות הבזבוז:בין 20 ל700 ישנם 117 מספרים ראשוניים (בדיקה ע"י מחשב). אם הינו בודקים במצב הגרוע ביותר עד מחצית המספר אז היינו בודקים 349 מספרים - אכן יש כאן בזבוז.אבל הבזבוז הזה מתגמד לעומת 200 תאי זיכרון שנקציב למערך שישמור את כל המספרים הראשוניים (הרי אנחנו לא יודעים כמה מספרים באמת קיימים, לכן נקציב מספר גבוה ונשאיר תאים ריקים).לעומת זאת אם היינו בודקים רק עד שורש המספר, במצב הגרוע ביותר היינו סורקים 25 מספרים בלבד(מ2 עד 26[שורש ריבועי טבעי של 700])!אך כאן יש חישוב שורש שהוא דיי מסורבל...
פורסם 2004 בספטמבר 721 שנים כן אבל יש פגם אחדאתה יודע איך פעולת שורש עובדת במחשב??משום מה יש לי הרגשה שהיא בעצמה עושה נסיונות וצורכת המון משאביי מערכתבכל מקרה אי אפשר להימנע מזהבסופו של דבר המחלק הראשון של כל מספר בר חלוקה הוא מספר ראשוני כלומר אם תרצה לבדוק מספר נורא גבוה שהוא במקרה ראשוני אתה בטוח תעבור את כל המספרים הראשוניים עד חציוהשאלה מה יותר יקרזיכרון או זמן מעבד?
פורסם 2004 בספטמבר 721 שנים שאלה ממש טובה... הייתי אומר שבשביל תוכנית של תלמיד הלומד מדעי המחשב הדבר החשוב ביותר הוא פיתרון חכם, יצירתי ויעיל מכל הבחינות. 8)
פורסם 2004 בספטמבר 721 שנים נכוןאני חושב שאם מורה רואה דרך יצירתית הוא ישר רואה את התלמיד בצורה אחרתהוא רואה שהתלמיד חושב ולא סתם עובד כמו תוקי שהיה בודק אחד אחד את כל המספרים עד המספר המבוקשנכון שהתוכנית הייתה עובדת אבל מה עשינו פה?לפי דעתי ווגה קח פה את כל הרעיונות שנאמרו ותציג למורה שלך מספר אפשרויות שונות לפיתרוןאני בטוח שתקבל על זה הערכה נוספת
פורסם 2004 בספטמבר 821 שנים שורש של מחשב הוא לא פעולה בזבנית כל כך ואני די בטוח שהיא פחות בזבזנית מלולאההמחשב לא "מנחש" את השורש יש טור מתמ' שהוא משתמש בו ואם אתה מנסה לחשב שורש אינטג'רי אני חושב שהטור הוא בעל 3 או 4 איבריםמה שיוסיף רק 3 או 4 איטרציות יותר פר מספר אבל יחסוך 100+ איטרציות של לעבור על המספרים עד החצי
פורסם 2004 בספטמבר 821 שנים TeaTime צודק בהחלט. לבצע איטרציה על כל המספרים יהיה הרבה הרבה הרבה הרבה יותר בזבזני. קחו מספר כמו n=10^20=100000000000000000000. כמות האיטרציות עד n*0.5 תהיה 0.5n=0.5*10^20=50000000000000000000 כמות האיטרציות עד(sqrt(n תהיה 10000000000 =10^10=(sqrt(n חישוב השורש יקח (ונהיה large) מקסימום 10 איטרציות. היחס בין הכמויות הוא 50000000000000000000 / (10000000000 + 10) = ~5000000000 = 0.5*10^10 כלומר אם היה לוקח לבצע את האלגוריתם של השורש שניה אחת האלגוריתם עד החצי היה לוקח (שימוש קל במחשב ) 1388888 שעות שהם 57870 ימימ שהם 158 שנים!!!!!!! לגבי הרעיוך להשתמש בחלוקה רק במספרים שידוע כבר שהם ראשוניים (ע"י Burton) מעולה!!!! הרעיון כמובן לא חדש ומבוסס על הנפה של אריסטוטנס( :ylsuper:) והרעיון הוא בדיוק מה ש - Burton אמר. לגבי המקום שזה ידרוש (והעובדה שגודל זה לא ידוע מראש). נתחיל מזה שהגודל אותו צריך להקצות לא ידוע מראש: אין שום בעיה יש הרבה סוגים של מבני נתונים (אוביקטים שמכילים נתונים[כמו מספרים]) ש"יודעים" לגדול בצורה דינאמית. דבר שני הגודל כן ידוע מראש, או ליתר דיוק כמעט ידוע מראש והוא בערך (log(n . ומובטח שם עולמי למי שגם יוכיח זאת אבל זה כבר ענין לפורם מתמטי ) לגבי המקום: אין שום בעיה כי כמעט בכל המקרים יעילות האלגוריתם מבחינת הזמן הרבה יותר חשובה יעילות האלגוריתם מבחינת כמות הזיכרון שהוא תופס (וזה אכן מדד חשוב). כל חברה תעדיף לשלם עוד 1000$ על זיכרון מאשר עוד שנת זמן ריצה כדי לחכות שהתוכנית תסתים - יש לי הרגשה שגם אתם . בסדר, נכון , אני מסכים שענין תאורטי/אקדמי לחלוטין וכבר בטח Vega קיבל 100 אבל סתם בא לי. וכדי שלא תגידו אז יש לי שיפור לתוכנית שיחסוך עוד פקטור של חצי והוא לקדם את i ב-2 כל פעם ולא ב-1 כלומר בלולאה לעשות i+=2 במקום i++ (כמובן שרק אחרי שבדקנו שהמספר איונ מתחלק ב-2) וזאת, כי אכן אין טעם לחלק באיזה מספר זוגי כלשהו מרגע שראינו ש 2 הוא אינו מחלק.
פורסם 2004 בספטמבר 821 שנים לא רק שחישוב שורש לוקח הרבה יותר מ-10 איטרציות פעולות על מספרים עם נקודה צפה איטיים במידה ניכרת.שורש ריבועי מחושב ע"י טור המתכנס אליו, אבל החישובים על הטור הם חישובים על מספרים עם נקודה צפה, ואלה חישובים מאד יקרים.יכול אולי להיות שעבור מספרים מאד גדולים כדאי כבר לחשב את השורש, אבל ממילא אין לך אפשרות לשמור מספר גדול כל כך.
פורסם 2004 בספטמבר 821 שנים הטור מתכנס במהירות אדירה ואפשר לחשב אותו אינטג'ריתמה שמאפשר 2-3 איטרציות עד לתשובה של 0.1 מהאמיתית (כלומר האינטג'ר עצמו)גם אם משתשים בחישובי הנקודה הצפה 2 האיטרציות הראשונות נשארות אינטג'ריות תמיד (במספרים שלמים כמובן)(ככה מתנהג הטור ואני די בטוח שככה המחשב משתמש בו כדי לחסוך) ככה שרק האיטרציה השלישית ומעלה נהיות צפותומכיוון שהדיוק שמחפשים הוא אינטג'רי רק האיטרציה הראשונה שהיא נקודה צפה תבוצע (הוא מבצע אותה ומבין שהגיע לדיוק הנדרש)
פורסם 2004 בספטמבר 821 שנים לגבי הרעיוך להשתמש בחלוקה רק במספרים שידוע כבר שהם ראשוניים (ע"י Burton) מעולה!!!! הרעיון כמובן לא חדש ומבוסס על הנפה של אריסטוטנס( :ylsuper:) והרעיון הוא בדיוק מה ש - Burton אמר. תודה תודה ;D האמת שחשבתי עליו בעצמי אבל כששאלתי את אבא שלי גם הוא העלה את אותו רעיון ועכשיו אתה גם אומר שזה דבר מוכר(האמת לא שיערתי שאני הראשון אבל זה היה בלתי תלוי) דרך אגב אבא שלי אמר לי שיש שיטות הרבה יותר יעילות שמשתמשות בהסתברות כדי לקבוע אם בכלל כדאי להשתמש באלגוריתם המלא יש מקרים שההסתברות קובעת מראש שבכלל לא כדאי ואפשר מראש לשלול את המספר אם תירצו אני מחר אברר עוד בנושא ההסתברות
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.