Author: gutner

מתוך 
סמסטר א'  תשס"ח
 4 בספטמבר  2008
מבחן סיום מועד ג' - מבוא למחשבים לסטטיסטיקאים
0365.1800
שי גוטנר

משך המבחן: שלוש שעות.

הנחיות כלליות:
1.	חומר עזר: דף A4 אחד הכתוב בשני צדדיו.
2.	יש לענות בדפי התשובות בלבד.
3.	טופס המבחן ומחברת המבחן ישמשו כטיוטא ולא ייבדקו.
4.	יש לענות על כל השאלות.

בהצלחה !!!

שאלה 1 ( 25 נק' )

סעיף א' ( 22 נק' )

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

כחלק מהתוכנית חובה לממש את הפונקציה הבאה:
double average_height(player p[ ],int n);

הפונקציה average_height מקבלת כקלט מערך p של n רשומות של שחקנים ומחזירה את ממוצע גובהי השחקנים.
חובה להחזיק בזיכרון נתונים לגבי שחקן אך ורק באמצעות רשומות מהטיפוס player שהגדרתם. אינכם רשאים להניח שקיים חסם למספר השחקנים.

דוגמה:
קלט:
14
Fanan			4		1981		183		Israel
Baston			5		1976		206		USA
Sharp			6		1971		183		Israel
Vujcic			7		1978		211		Croatia
Parker			8		1975		198		USA
Shelef			9		1974		201		Israel
Burstein		10		1980		198		Israel
Halperin		11		1984		193		Israel
Dotan			12		1974		194		Israel
Jasikevicius		13		1976		193		Lithuania
Caspi			14		1988		203		Israel
Kommatos		20		1977		203		Greece
Thomas		25		1971		204		Israel
Green			41		1980		206		Israel

פלט: 
Average height = 198.285714
Baston			5		1976		206		USA
Vujcic			7		1978		211		Croatia
Shelef			9		1974		201		Israel
Caspi			14		1988		203		Israel
Kommatos		20		1977		203		Greece
Thomas		25		1971		204		Israel
Green			41		1980		206		Israel		

הערות:

1.	ניתן להניח כי הקלט חוקי.
2.	הקפידו לשחרר זכרון אותו הנכם מקצים.

סעיף ב' ( 3 נק' )

מה סיבוכיות זמן הריצה של התוכנית אותה כתבתם בסעיף א'?
אין צורך לנמק את התשובה.

שאלה 2 ( 25 נק' )

סעיף א' ( 18 נק' )

כתבו פונקציה כדלהלן:

int count_perfect(int n);

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

לדוגמה, count_perfect(9000) תחזיר את הערך 4, שכן יש ארבעה מספרים מושלמים קטנים מ-9000, כדלהלן:
6, 28, 496, 8128

הפונקציה צריכה להיות יעילה ככל האפשר מבחינת זמן ריצה.

כחלק מהפתרון, חובה לכתוב פונקציה כדלהלן:  
int sum_of_dividers(int n);

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

בפתרון של השאלה אין לעשות שימוש בפונקציות ספריה.

סעיף ב' ( 7 נק' )

נתחו את סיבוכיות זמן הריצה של הפונקציה count_perfect אותה מימשתם בסעיף א' כתלות בפרמטר n.

שאלה 3 ( 15 נק' )

סעיף א' ( 12 נק' )

כתבו פונקציה רקורסיבית כדלהלן:

int max_value(int a[ ],int n);

הפונקציה מקבלת כקלט מערך a של n  מספרים שלמים, ומחזירה את הערך המקסימאלי המופיע במערך זה.

ניקוד חלקי יינתן למימוש שבו הפונקציה max_value איננה פונקציה רקורסיבית.

סעיף ב' ( 3 נק' )

מה סיבוכיות זמן הריצה של הפונקציה אותה מימשתם בסעיף א' כתלות בפרמטר n?
אין צורך לנמק את התשובה.

שאלה 4 ( 15 נק' )

כתבו פונקציה כדלהלן:
int exactly_once(int a[ ],int n,int x);

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

הפונקציה צריכה להיות יעילה ככל האפשר מבחינת זמן ריצה.

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

שאלה 5 ( 10 נק' )

כתבו פונקציה כדלהלן:
void copy_to_upper(char *t,char *s);

הפונקציה מעתיקה לתוך t את המחרוזת s, והופכת כל אות אנגלית קטנה לאות האנגלית הגדולה המתאימה.

לדוגמה, אם s היא המחרוזת "BoraBora1+2+3*4*5", אז לתוך t תועתק המחרוזת "BORABORA1+2+3*4*5".

הערות:

1.	המימוש של הפונקציה יעשה ע"י שימוש במצביעים בלבד (אסור להגדיר משתנים מטיפוס שאינו מצביע, כמו למשל int או double).
2.	אסור לעשות שימוש בסוגריים מרובעים.  
3.	אין לבצע קריאה לפונקציות אחרות מתוך הפונקציה (בפרט, אסור להשתמש בפונקציות ספריה).

שאלה 6 ( 10 נק' )

כתבו פונקציה כדלהלן:
int equal_rows_sum(int a[10][20]);

הקלט לפונקציה הוא מטריצה a בגודל 10׳20 של מספרים שלמים. הפונקציה צריכה להחזיר 1 אם לכל עשר השורות של המטריצה יש את אותו סכום איברים, ואפס אחרת.

בהצלחה !!!

נספחים:

Precedence and Associativity of Operators

Table 1 summarizes the rules for precedence and associativity of all operators. Operators on the same line have the same precedence; rows are in order of decreasing precedence, so, for example, *, /, and % all have the same precedence, which is higher than that of binary + and -. 

Operators | Associativity
() [] -> . | left to right
! ~ ++ -- + - * & (type) sizeof | right to left
* / % | left to right
+ - | left to right
<<  >> | left to right
< <= > >= | left to right
== != | left to right
& | left to right
^ | left to right
| | left to right
&& | left to right
|| | left to right
?: | right to left
= += -= *= /= %= &= ^= |= <<= >>= | right to left
, | left to right
Unary &, +, -, and * have higher precedence than the binary forms. 
Table 1: Precedence and Associativity of Operators 

Standard Library Functions

Input and Output: <stdio.h>

int printf(const char *format, ...) 
The printf function provides formatted output conversion. 
int scanf(const char *format, ...) 
The scanf function deals with formatted input conversion. 

String Functions: <string.h>
In the following table, variables s is of type char *; cs and ct are of type const char *; and c is an int converted to char. 
char *strcpy(s,ct) | copy string ct to string s, including '\0'; return s.
char *strcat(s,ct) | concatenate string ct to end of string s; return s.
int strcmp(cs,ct) | compare string cs to string ct, return <0 if cs<ct, 0 if cs==ct, or >0 if cs>ct.
char *strchr(cs,c) | return pointer to first occurrence of c in cs or NULL if not present.
char *strstr(cs,ct) | return pointer to first occurrence of string ct in cs, or NULL if not present.
size_t strlen(cs) | return length of cs.
In the following table, s is of type void *; ct is of type const void *; n is of type size_t; and c is an int converted to an unsigned char. 
void *memcpy(s,ct,n) | copy n characters from ct to s, and return s.
void *memset(s,c,n) | place character c into first n characters of s, return s.

Mathematical Functions: <math.h>
In the following table, x and y are of type double, and all functions return double. 
exp(x) | exponential function e^x
log(x) | natural logarithm ln(x), x>0.
log10(x) | base 10 logarithm log_10(x), x>0.
pow(x,y) | x^y. A domain error occurs if x=0 and y<=0, or if x<0 and y is not an integer.
sqrt(x) | square root of x, x>=0.
fabs(x) | absolute value |x|

Utility Functions: <stdlib.h>

double atof(const char *s) 
atof converts s to double. 
int atoi(const char *s) 
converts s to int. 
int rand(void) 
rand returns a pseudo-random integer in the range 0 to RAND_MAX, which is at least 32767. 
void srand(unsigned int seed) 
srand uses seed as the seed for a new sequence of pseudo-random numbers. The initial seed is 1. 
void *malloc(size_t size) 
malloc returns a pointer to space for an object of size size, or NULL if the request cannot be satisfied. The space is uninitialized. 
void free(void *p) 
free deallocates the space pointed to by p; it does nothing if p is NULL. p must be a pointer to space previously allocated by malloc. 
int abs(int n) 
abs returns the absolute value of its int argument. 

Date and Time Functions: <time.h>

time_t time(time_t *tp) 
time returns the current calendar time or -1 if the time is not available. If tp is not NULL, the return value is also assigned to *tp.