Author: gutner
Last saved by: HUCA

מתוך 
סמסטר ב'  תשס"ז
 6 בספטמבר 2007
מבחן סיום מועד ב' - מבוא כללי למדעי המחשב
0366.1106
שי גוטנר

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

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

בהצלחה !!!

שאלה 1 ( 25 נק' )

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

כתבו תוכנית הקולטת מספר טבעי n ורשומות של n מניות הנסחרות ב-NASDAQ ומדפיסה נתונים של מניה ושנה מסוימת שבה השינוי (בערך מוחלט) באחוזים של מחיר המניה היה הגבוה ביותר. 
הגדירו טיפוס נתונים בשם stock לתחזוקת שם החברה, סמל המניה, שווי השוק של החברה (מספר ממשי, במיליארדי דולרים), שנה ראשונה שבה התחילה להיסחר, מספר השנים שבהם היא נסחרת וכן נתונים לגבי מחיר המניה (מספר ממשי חיובי, בדולרים) בסוף חודש דצמבר של כל שנה. ניתן להניח כי האורך של שם חברה הוא לכל היותר 30 וכי האורך של סמל מניה הוא בדיוק 4.

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

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

double maximum_change(stock *s,int *year);

דוגמה:

קלט:

13
Microsoft	MSFT		295.63	1986	21	0.14 0.33 0.32 0.52 0.9 2 2.3 2.18 3.3 4.74 8.92 13.95 29.94 50.41 18.73 28.61 22.32 23.84 26.02 25.78 29.86
Cisco		CSCO		164.81	1990	17	0.16 0.46 1.09 1.79 1.95 4.15 7.07 9.29 23.2 53.56 38.25 18.11 13.1 24.23 19.32 17.12 27.33
Google		GOOG		147.41	2004	3	192.79 414.86 460.48
Intel		INTC		122.41	1986	21	0.41 0.77 0.69 1.01 1.12 1.43 2.54 3.63 3.76 6.69 15.48 16.63 28.12 39.11 28.6 30 14.91 30.8 22.62 24.46 20.25
Oracle		ORCL		90.27	1988	19	0.24 0.58 0.19 0.36 0.7 1.42 2.18 3.14 4.64 3.72 7.19 28.01 29.06 13.81 10.8 13.23 13.72 12.21 17.14
Apple		AAPL		72.90	1984	23	3.32 2.51 4.62 9.63 9.31 8.23 10.17 13.46 14.39 7.13 9.64 7.97 5.22 3.28 10.23 25.7 7.44 10.95 7.16 10.69 32.2 71.89 84.84
Dell		DELL		52.43	1988	19	0.1 0.06 0.19 0.27 0.75 0.35 0.64 1.08 3.32 10.5 36.6 51 17.44 27.18 26.74 33.98  42.14 29.95 25.09
eBay		EBAY		45.17	1998	9	10.05 15.65 8.25 16.73 16.95 32.31 58.17 43.22 30.07
Yahoo		YHOO		39.13	1996	11	0.71 4.33 29.62 108.17 15.03 8.87 8.18 22.51 37.68 39.18 25.54
Sun		SUNW		23.37	1987	20	0.52 0.52 0.54 0.67 0.89 1.05 0.91 1.11 2.85 3.21 4.99 10.7 38.72 27.87 12.3 3.11 4.47 5.39 4.19 5.42
Symantec	SYMC		16.94	1990	17	1.67 5.56 1.7 2.28 2.19 2.91 1.81 2.74 2.72 7.33 4.17 8.29 10.13 17.25 25.76 17.5 20.85
Akamai	AKAM	8.69	1999	8	327.63 21.06 5.94 1.73 10.76 13.03 19.93 53.12
SanDisk	SNDK		8.02	1995	12	3.75 2.44 5.08 3.53 24.06 13.88 7.2 10.15 30.6 24.97 62.82 43.03

פלט: 

Yahoo	YHOO Dec 1997 price: $4.33 Dec 1998 price: $29.62 Change: 584.06%

הערות:

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

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

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

שאלה 2 ( 25 נק' )

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

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

int count_perfect(int n);

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

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

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

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

שאלה 3 ( 15 נק' )

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

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

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

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

שאלה 4 ( 15 נק' )

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

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

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

שאלה 5 ( 10 נק' )

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

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

הפונקציה מחזירה 1 אם המחרוזות s ו-t הינן זהות, ואפס אחרת.

הערות:

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

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

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

שאלה 6 ( 10 נק' )

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

דוגמאות:

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

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

בהצלחה !!!

נספחים:

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.