Title: Scheme - Final Exam - Spring 2000
Author: Uri Zwick
Last saved by: gutner

מתוך 
סמסטר א' תשס"ד
20 בנובמבר  2003
תרגיל 2 - מבוא למחשבים לסטטיסטיקאים
0365.1800
שי גוטנר

תאריך הגשה: 4 בדצמבר 2003.

שאלה 1

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

דוגמא:
קלט: 3000
פלט:
220 , 284
1184 , 1210
2620 , 2924

שאלה 2

ודאו כי כאשר מייצגים מספרים שלמים בשיטת המשלים ל-2 ע"י 8 ביטים מתקיים:

א)	(-106) + 73 = -33
ב)	(-12) * 9 = -108

שאלה 3

מימוש נפת אריסטוסטנס: כתבו תוכנית הקוראת מספר שלם אי שלילי n, ומדפיסה את כל המספרים הראשוניים הקטנים או שווים ל-n. ניתן להניח כי .
מה סיבוכיות זמן הריצה?

דוגמא:
קלט: 9
פלט: 
2
3
5
7
There are 4 prime numbers lower or equal to 9

שאלה 4

מיינו את הפונקציות הבאות על פי קצב גדילתן האסימפטוטי:

         

בהצלחה !!!