מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 2

לדף הקורס

תרגיל שני - לולאות ומערכים

מועד הגשה: יום חמישי ה 17.11.11

האם מספר מסויים הוא ראשוני?

כיתבו תוכנית בשם q1.c המקבלת מהמשתמש מספר ובודקת אם הוא ראשוני. סיבוכיות התוכנית צריכה להיות <m> O(\sqrt{n}) </m> כאשר n הוא גודל המספר שהוכנס. התנהגות התוכנית שלכם צריכה להיות זהה להתנהגות של קובץ ההרצה הזה (זכרו שיש לתת לו הרשאת ריצה באמצעות chmod +x)

כל הראשוניים עד ל n

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

סדרת פיבונאצ'י

סדרת פיבונאצ'י היא סדרה ששני האברים הראשונים שלה שווים ל 1 וכל איבר אחר שווה לסכום קודמיו. לדוגמה, האברים הראשונים של הסדרה הם:

1, 1, 2, 3, 5, 8, 13, ...

פרטים נוספים על הסידרה, ניתן למצוא כאן.

כיתבו בקובץ q3.c תוכנית המכינה מערך המכיל את 30 האברים הראשונים של סדרת פיבונאצ'י ומאפשרת למשתמש לבדוק את ערכי הסדרה השונים. באופן מחזורי, המשתמש יכניס אינדקס של הסידרה ויקבל את הערך של האבר בעל האינדקס הזה. בכדי לצאת מההרצה, המשתמש יכניס את הערך 0. הרצה לדוגמה:

(enter 0 to quit) i: 4
F(4)=3
(enter 0 to quit) i: 7
F(7)=13
(enter 0 to quit) i: 0

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

אלגוריתם הנפה של ארטוסתנס

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

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

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

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

שימו דגש על יעילות הקוד שלכם. קובץ הקוד של שאלה זו יקרא q4.c .

השוואת מהירויות

בשאלה זו אתם מתבקשים לכתוב תוכנית שתאפשר להשוות את ביצועי האלגוריתם שכתבתם בשאלה 2 לזה שכתבתם בשאלה 4.

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

init_time();

שגורמת להתחלת מדידה של זמן. והפקודה:

printf("%lld\n",get_time());

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

כיתבו בקובץ q5.c קוד שמבקש מהמשתמש להכניס מספר, מריץ את האלגוריתם משאלה שתיים ומודד את הזמן שלו ואז מריץ את האלגוריתם של הנפה משאלה 4 ומודד את הזמן שלו. במקום להדפיס את כל הראשוניים עד המספר שהכניס המשתמש, יש להדפיס רק כמה ראשוניים כאלה קיימים. קובץ ההרצה הזה מדגים איך אמורה להראות ההרצה של הקוד שלכם. הזמנים יכולים להיות שונים כי הם תלויים במימוש הספציפי ובגורמים נוספים.

הגשה

בדומה להגשת התרגיל הקודם, יש ליצור קובץ ex2.tgz המכיל את הקבצים q1.c, q2.c, q3.c, q4.c ו q5.c המכילים את הפרטים האישיים שלכם. ההגשה במטלה "תרגיל שני" בדף הקורס במודל. אל תשכחו ולבצע את הבדיקה שהקובץ שאתם מגישים אכן כולל את כל הקבצים הנדרשים (להעתיק לתקיה נפרדת, לחלץ, להדר את כולם ולהריץ).

בתרגיל זה אין בונוס.

בהצלחה!

פיתרון

q1.c

#include <stdio.h>
#includ
    int prime = 1; 
    for(i=2; i <= sqrt(n); ++i)
	if(n%i == 0) {
	    prime = 0;
	    break; 
	}
    if (prime) 
	printf("%d is prime\n",n);
    else 
	printf("%d is *not* prime\n",n);

    return 0;
}

q3.c

#include <stdio.h>

int main() {
    const int N = 31;
    int i; 
    int ar[N]; 
    ar[1] = 1; 
    ar[2] = 1; 

    for(i=3; i<N; ++i)
	ar[i] = ar[i-2]+ar[i-1]; 

    while(1) {
	printf("(enter 0 to quit) i: "); 
	scanf("%d",&i); 
	if(i < 1 || i>=N)
	    break; 
	printf("F(%d)=%d\n",i,ar[i]); 
    }
    return 0; 
}

q4.c

#include <stdio.h>
#include <math.h> 

int main() {

    const int MAX = 1e6+1; 
    char ar[MAX]; 
    int n,i,j; 

    while(1) {
	printf("n: "); scanf("%d",&n);
	if(n < MAX) 
	    break; 
	printf("n should be < %d\n",MAX); 
    }

    printf("All primes <=%d:\n",n); 

    for(i=0; i<=n; ++i)
	ar[i] = 't'; 
    
    i = 2;  
    while (i<=sqrt(n)) {  

	for(j=i*i; j<=n; j+=i) 
	    ar[j] = 'f'; 

	do {
	    ++i;
	} while(i <= sqrt(n) && ar[i] == 'f');  
    }

    for(i=2; i<=n; ++i)
	if(ar[i] == 't')
	    printf("%d, ",i); 

    printf("\n"); 

    return 0;
}

q5.c

#include <stdio.h>
#include <math.h> 

#include <sys/time.h> 

static struct timeval start_time;
typedef long long int64;

void init_time() {
    gettimeofday(&start_time, NULL);
}

int64 get_time() {
    struct timeval t;
    gettimeofday(&t, NULL);
    return (int64) (t.tv_sec - start_time.tv_sec) * 1000000
	+ (t.tv_usec - start_time.tv_usec);
}



int main() {
    const int MAX = 1e6+1; 
    char ar[MAX]; 
    int n, i, j, countNaiv=0, countSieve=0; 

    while(1) {
	printf("n: "); scanf("%d",&n);
	if(n < MAX) 
	    break; 
	printf("n should be < %d\n",MAX); 
    }
    // Naive 
    init_time(); 
    for(i=2; i<=n; ++i) {
	int isPrime = 1; 
	for(j=2; j <= sqrt(i); ++j)
	    if(i%j == 0) {
		isPrime = 0;
		break; 
	    }
	if (isPrime) 
	    ++countNaiv; 
    }

    printf("Naive algorithm took %lld microseconds.\n",get_time()); 
    printf("Found %d primes\n",countNaiv); 

    // Sieve 

    init_time(); 
    for(i=0; i<=n; ++i)
	ar[i] = 't'; 
    
    i = 2;  
    while (i<=sqrt(n)) {  

	for(j=i*i; j<=n; j+=i) 
	    ar[j] = 'f'; 

	do {
	    ++i;
	} while(i <= sqrt(n) && ar[i] == 'f');  
    }

    for(i=2; i<=n; ++i)
	if(ar[i] == 't')
	    ++countSieve; 

    printf("Sieve algorithm took %lld microseconds.\n",get_time()); 
    printf("Found %d primes\n",countSieve); 

    return 0;
}

לדף הקורס