פורסם 2005 בנובמבר 1120 שנים שלום לכלום המורה הביא לנו תרגילים לפתור ב c++ אם תוכלו לעזור אני אודה לכם מאוד תרגיל אחד זה כתוב תוכנית הקולטת מספר n ובודקת אם הוא ראשוני.. תרגיל שני כתוב תוכנית הקולטת מספר n ומציגה את כל המספרים הראשוניים בין 1 ל n חשבתי הרבה כיצד אני אוכל לעשות זאת ולא הצלחתי למצוא פיתרון ... תודה מראש למי שעוזר
פורסם 2005 בנובמבר 1120 שנים אני מניח שלמדתם פונקציות ושהתכוונו שתעשו את זה עם פונקציות.תוכנית ראשונה:[code=cpp][code]#include <iostream.h>int ri(int n){ for(int i=2;i<n/2;i++) if(n%i==0) return 0; return 1;}void main(){ int n; cout<<"Please enter a number."<<endl; cin>>n; if(ri(n)==0) cout<<"The number is parik."<<endl; else cout<<"The number is rishoni."<<endl;}תוכנית שנייה:[code]#include <iostream.h>int ri(int n){ for(int i=2;i<n/2;i++) if(n%i==0) return 0; return 1;}void main(){ int n; cout<<"Please enter a number."<<endl; cin>>n; for(int i=1;i<=n;i++){ if(ri(i)==0) cout<<"The number "<<i<<" is parik."<<endl; else cout<<"The number "<<i<<" is rishoni."<<endl; }}עריכה: יש צורך רק לתקן לגבי המספר 1 שהוא לא ראשוני ולא פריק ו-0 שהוא לא חוקי.
פורסם 2005 בנובמבר 1120 שנים ובמקום לחלק את -N ב-2 אפשר לעשות גם שורשהיה על זה ויכוח פעם מה יותר יעיל
פורסם 2005 בנובמבר 1120 שנים פתרון עבור הראשון:http://en.wikipedia.org/wiki/Fermat_primality_testיש עוד מבחני ראשוניות יותר מורכבים (שגם צודקים בהסתברות יותר גבוהה).פתרון עבור השני:בונים מערך עם המספרים 0 עד n ומאפסים את מקום 1 (ככה שהמערך הוא 0,0,2,3,4...)עכשיו עבור כל תא במערך:- אם התא מכיל 0, נדלג לתא הבא.- אחרת, נאפס התאים בכל הכפולות של אותו מקום (למעט אותו תא) (כלומר אם אנחנו ב-3, אז נאפס את תאים 6,9,12,15, וכן הלאה)בסופו של דבר כל התאים שאינם 0 הם מספרים ראשוניים.
פורסם 2005 בנובמבר 1320 שנים מחבר התוכניות עובדות די בסדר אבל שאני שם את המספר 4 הוא אומר לי שהוא ריאשוני אז יש פה טעות איפשהוא
פורסם 2005 בנובמבר 1520 שנים ובמקום לחלק את -N ב-2 אפשר לעשות גם שורשהיה על זה ויכוח פעם מה יותר יעילבקשר לתרגיל הראשון - ברור שלרוץ עד שורש N זה הרבה יותר יעיל מאשר לרוץ עד N/2 (קח למשל N = 1,000,000 וכבר תראה הבדל בפועל).תרוץ על i קטן-שווה לשורש N (כי אחרת 25 יעשה בעיה. אולי זו הבעיה שיש לך עם 4).שיפור נוסף למה ש- orlupo הציע: תבדוק האם המספר מתחלק ב-2 בנפרד. בלולאה תרוץ מ-3 ומעלה, ובמקום++ iתעשה2 =+ iאין טעם לבדוק עבור 4,6,8... וכו' כי כולם זוגיים. ככה עושים רק חצי מהבדיקות.בקשר למה ש-שניצל אמר: מדובר באלגוריתמים הסתברותיים [זה הכרחי כי לפעמים המספרים גדולים מאוד ואי אפשר לבדוק ראשוניות בשיטה הנאיבית וחייבים להסתמך על כל מיני היבטים מתמטיים תאורטיים]. זה נושא מאוד עמוק ודי מסובך ואתה ממש, אבל ממש, לא רוצה להכנס לזה בשביל תרגילון קטנטן ב- c++ !
פורסם 2005 בנובמבר 1520 שנים אבל עצם החישוב של השורש יכול לקחת יותר זמן מזמן הריצה של הלולאה...בדיוק על זה התווכחנו אז
פורסם 2005 בנובמבר 1520 שנים אבל עצם החישוב של השורש יכול לקחת יותר זמן מזמן הריצה של הלולאה...ממש, אבל ממש לא סביר (עבור בעיות "מעניינות").אין לי מידע ספציפי לגבי זמני החישוב, אבל אם נדבר ברמה אחת מעל זה: את שורש N צריך לחשב פעם אחת. גם אם זו לא פעולה אחת, זה מספר לא רב של פעולות.גם את N/2 צריך לחשב, במיוחד אם מחשבים את זה כל פעם שבודקים את הלולאה ולא פעם אחת לפניה, אבל בכל מקרה גם זה לוקח זמן. סביר להניח שהפרש הזמנים בין שתי פעולות החישוב הוא זניח.בד"כ לא יעניין אותנו להסתכל על מספרים קטנים מאוד, וגם אם כן עדיין זמן החישוב הכולל יהיה פחות משניה, אז מה זה חשוב על מה הלך רוב הזמן?אם מסתכלים על מספרים גדולים - יהיה יתרון גדול לחסוך הרבה איטרציות של הלולאה (לדעתי כבר ממליון זה יהיה מורגש, אבל תחשבו מה זה אומר לבדוק ראשוניות של מספר בן 20, 30, או 1024 ביטים...)
פורסם 2005 בנובמבר 1620 שנים לכן כדאי לבדוק אילו גדלי קלט אנו מקבלים כדי להתאים את התוכנית. אם אנו מקבלים מספרים קטנים, מומלץ לחלק ב- 2. אם אנו מקבלים מספרים גדולים, כדאי למצוא את השורש...
פורסם 2005 בנובמבר 1620 שנים ניסיתי לחפש מידע על כמה פעולות לוקח לעשות את פעולות החישוב האלה ולא מצאתי.אבל אפילו אם מדובר במספר מאוד קטן, נגיד 100 :לרוץ עד שורש 100 זה 10 איטרציות של הלולאה.לרוץ עד 100/2 זה 50 איטרציות.מדובר בהפרש של 40 איטרציות במקרה הזה.בכל איטרציה של הלולאה אתה צריך לעשות: קידום של משתנה, בדיקה האם הגעת לתנאי העצירה, חישוב פעולת מודולו ובדיקת תנאי (האם תוצאת המודולו = 0).40 איטרציות * מספר הפעולות בכל איטרציה = המון המון פעולות שחוסכים (אל תשכחו שאפילו משהו פשוט כמו i++ לוקח 3-4 פעולות מעבד).כך שלדעתי גם למספרים קטנים אנחנו נחסוך אם נרוץ רק עד השורש.כבר כמה כבר יכול להיות לחשב שורש? בכמה הוא יותר כבד מסתם חילוק?בכל מקרה, בניתוח זמני ריצה, בד"כ מסתכלים על זה כעל פעולה בודדת כי זה זניח לעומת שאר התוכנית (וגם בגלל שמי בכלל יכול לדבר על פעולות מעבד בסיסיות??).
פורסם 2005 בנובמבר 1620 שנים כבר כמה כבר יכול להיות לחשב שורש? בכמה הוא יותר כבד מסתם חילוק?כבד כבדבייחוד או השורש לא שלם
פורסם 2005 בנובמבר 1620 שנים כבר כמה כבר יכול להיות לחשב שורש? בכמה הוא יותר כבד מסתם חילוק?בכל מקרה, בניתוח זמני ריצה, בד"כ מסתכלים על זה כעל פעולה בודדת כי זה זניח לעומת שאר התוכנית (וגם בגלל שמי בכלל יכול לדבר על פעולות מעבד בסיסיות??).שורש זוהי לא פעולה בסיסית... זה שאתה יודע ששורש 9 זה 3 לא אומר שהמחשב יודע את זה. אתה יכול לתכנן מעבד שמחשב שורשים(כפי שהוא מתוכנן לחשב חלוקה) ואז זה יהייה אולי יעיל יותר.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.