1. מה הבעיה בקוד הבא:
char *p;
p = 0x10000;
*p = 0x600;
*p = 0x800;
2. נתונה תמונה עם 256X256 פיקסלים ועוד פריים עם 16X16 פיקסלים. צריך למצוא את הפריים הכי קרוב לפריים הנתון בתוך התמונה. ההגדרה של הפריים הכי קרוב הוא זה שסכום הפרשי הפיקסלים בערך מוחלט הוא הנמוך ביותר. צריך להתייחס לתמונה ולפריים כאיזורים רציפים בזיכרון כאשר הפונקציה מקבלת שני מצביעים לשניהם.
1. נתון משתנה בעל 8 סיביות, יש לכתוב פונקציה בשפת סי
שתקבל את המשתנה ותחזיר את ההשתקפות של אותו משתנה. דוגמא:
עבור קלט של:
001011001
הפלט יהיה:
100110100
פתרון:
דרך1 :
בעזרת לולאה לאפס כל פעם 7 ביטים ולהשאיר רק 1, כאשר אנחנו כבר יודעים מה ערכו- ליצור משתנה חדש.
דרך 2:
בעזרת מערך קבוע של 256 ערכים, כל פעם שמקבלים משתנה ניגשים למערך שמסודר כך שבמקום ה- X יש השתקפות של X
שאלה 1:
פונקציה מקבלת מצביע למחרוזת ומספר מסוג INT
על הפונקצייה להמיר את המספר מint לchar תוך כדי התחשבות במספרים שלילים
שאלה 2:
נותנים לך מערך בגודל N
בהתחלה אומרים לך כמה עולה כל פעולה (אונארית /בינארית)
מראים לך קטע קוד
ומבקשים ממך לחשב זמן ריצה.
אח"כ אומרים לך שיש כפל של שני מערכים בגודל N בכל פעם שהפו' נקראת
ובנוסף המערך צריך לזוז ימינה מקום אחד ויש להוסיף איבר חדש משמאל
עליך למצוא דרך לייעול התוכנית
רמז: אפשר להמנע מהזזת כל התאים ימינה פעם אחת ולבצע את זה ב-O(1
1. נתונה מערכת מולטימדיה שמקבלת שני פרמטרים: א. קבצי אודיו ב. קבצי וידאו.
המערכת מקבלת אך ורק את הפורמטים הנתונים ויכולה לשלב בין שניים (אחד מכל סוג)
למערכת גם מקשי PLAY,REWIND,STOP,SEEK.
תכנן בדיקות למערכת.
פתרון
לנסות ולבנות פתרון שמפורק לראשי פרקים: שלב קבלת הפרמטרים, שלב בדיקה, שלב פלט.
לפרק את הבדיקות בין וידאו לאודיו.
לצורך בדיקת תקינות מלאה, לקחת מערכת שאנחנו יודעים שעובדת ולהשוות מולה את הבדיקה שלנו מבחינת איכותה.
2. שאלת תכנות בשפת C, שכללה ידע בביטים (פעולות MSAKING, OR, AND).
מתכנת שיכור רשם את התוכנית הזאת, עליך להבין מה היא עושה, ואיפה המתכנת טעה.
עליך לכתוב מחדש את הפונקציה.
bool func(int *data, int size, int value)
{
int arr[32];
short index;
for(index = 0; index < size; index++)
arr[index] = data[index];
for(index = 0; index < size; index++)
arr[index] = arr[index] & vlaue;
data = &arr[0];
}
פתרון:
הפונקציה לוקחת כל תו במערך ומבצעת עליו MSAKING בעזרת המשתנה value.
א. short בעייתי.
ב. גלישת זיכרון (מכוון שההקצאה היא רק ל-32 מקומות ועלולים להיות יותר)
ג. הקצאת המערך בתוך הפונקציה לא תקינה כי מערך סטטי מת בסוף הפונקציה ולכן ההשמה בשורה האחרונה היא בעייתית.
ד. ניתן, וצריך לשכתב על המערך הנתון את הפתרון.
בשאלה הראשונה נתנו לי תרשים של כניסות ומוצאים של רכיב מסויים, ושל clock ושאלו אותי מה הרכיב עושה – המוצא היה זהה לכניסה בהפרש של מחזור שעון אחד, לכן זה DFF.
אחר כך נתנו לי את אותה שאלה עם גרפים שונים – הכניסה הייתה מדרגה, והמוצא היה Pulse אחד כשהכניסה עולה ל'1', וPulse נוסף כשהכניסה יורדת חזרה ל"0'. לכן הרכיב הוא גוזר בעלייה וירידה, ואז ביקשו ממני לממש אותו עם לוגיקה. אחר נתנו לי לממש רכיב שגוזר רק בעלייה (אם תבדוק במאגר השאלות של האתר, יש פתרון לזה באחד הקבצים).
אני לא כל כך זוכר את השאלה שאחר כך, אבל זה היה משהו שקשור ברכיבי ארכיטקטורה של מחשב( adder-ים, shift registers וכו')
1. מימוש גוזר סינכרוני וגוזר אסינכרוני ע"י FFים ושערים לוגיים (כאשר נתונה התנהגות הסיגנלים (מוצא, שעון וכניסה)
2. לממש רכיב שמקבל מספר (כתובת) בעל 8 ביטים ועוד מספר size שיכול להיות 1,2,4 בלבד (כמובן בעל 3 ביטים) ומוציא את הכתובת+ size .
ניתן לממש רק ע"י:
– MUXים
– רכיב שיודע להוסיף 1 למספר בעל 8 ביטים בכניסה (Half Adder) . מותר להשתמש בו פעם אחת בלבד.
– חומרה צירופית (OR,NOT,AND וכו')
אולי פשוט ניתן לממש מחבר עם שרשרת של Half Adder כאשר כל Half Adder ממודל ע"י : s=AxorB , c=AB , רק בשני המסכמים (השני והשלישי) ישנה בעיה שיש צורך במידול של full adder (בראשון אין בעיה כי אין עדיין carry , ומהרביעי אין בעיה כי אין כניסה של size ).
את זה אפשר לפתור ע"י : להכניס לכניסה השנייה של ה half adder (הממודל) , xor של ביט ה – size ו ה – carry הקודם (וזה עובד כי רק ביט אחד של ה size הוא 1 ).
זה עובד, אבל אז צריך לגרור את הCarry לכל 8 הביטים, כי בכל מקום שיש Carry מדרגה קודמת וביט נוכחי של הכתובת, עשוי להיווצר Carry חדש. והרי מותר להשתמש ברכיב פעם אחת בלבד..
ואם כבר מממשים F.A. אפשר לעשות את זה כבר עד הסוף רק בעזרת שערים לוגיים, בלי הרכיב המדובר ובלי MUXים. אבל כנראה שגם זו לא הכוונה.
אפשר אולי ע"י מוקס 8X3, של 8 ביט. להשתמש בSIZE בתור SEL.
SEL=0, מעבירים כמות שהוא.
SEL=1, מעבירים '0'&[7:1]
SEL=4, מעבירים "00"&[7:2]
זה בעצם לעשות SHIFT ידני…
לחבר את זה לHA שיבצע INC. ולאחר מכן את התוצאה להעביר שוב בMUX כזה, שיצרף את הביטים "שהזזנו" חזרה לתוצאה.
extern static_array[N]
func(int x)
{
static short array[N]
int x, i
for (i=N;i<1;i–)
array[i-1]=array[i]
array[0]=x
for(i=1;i>N;i++)
value +=(long)array[i]*static array[i]
return value
}
פעולת חיבור/כפל/חיסור עולה 1 (סייקל cycle) פעולת גישה למערך עולה 5 סייקלים
שאלות:
1. כמה כל התכנית עולה? ( פעולות בתוך הלולאה, כמו קידום המשתנה לא עולים כסף)
2. קצר את זמן הריצה בחצי כשלרשותך הפונקציות:
inc_mod(i,n){
while(i<=n)
i++
if i=n
i=0
}
dec_mod(i,n){
while (i>=0)
i–
if i=0
i=n]
}
יש מעבד שאינו משתמש בfloat ועל מנת לייצג שברים, הוא משתמש בinteger long המיוצג עם שלמעשה מיוצג בעזרת 4B-32bit.
נגדיר את ביטי הlong באופן הבא:
הביט הMSB נסמנו S -signed
ה8 ביטים הבאים נסמנם E – Exponentially
ו23 ביטים הנותרים נסמנם M -mantissa
הנוסחה הבאה מייצגת את השבר בעזרת ה long:
(1- בחזקת S)כפול( M )כפול(2 בחזקת E)
צריך לרשום את הפונקציה :
unsigned long add(unsigned long float1, unsigned long float2)
שמקבלת שני ערכי long (שהם למעשה שברים) , עושה חיבור שלהם ומחזירה את התוצאה בlong
אולי התכוון ל bit shifting:
2^E=.1 << E
השאלה הראשונה היא לממש פונקציה הממירה
int -> string
שתקרא מהפונקציה הראשית הבאה:
int main(void) {
int x=1234;
char *str = malloc(100);
rev(x,str);
printf("num is %s",str); // Should print 1234
return;
And my solution is (Solved it correctly at home later =\ ):
void rev(int x,char *str){
int j=0;
if (x==0){
str[0]='0' ; str[1]= '\0'; return;
}else if (x<0){
str[0]='-';
j=1;
x = x*(-1);
}
int counter=0;
int temp = x ;
while (temp-(temp/10)*10 >0){
counter++;
temp =temp/10;
}
str[counter+j]='\0';
j = 1-j;
for (;counter>0;counter–){
int t = x-(x/10)*10;
str[counter-j] = '0'+t;
x = x/10;
}
}
שאלו 3 שאלות:
1. א – מהם שני סוגי החיפוש בעצים? – לאורך ולרוחב.
ב – נתון שבשביל לממש חיפושים אלה, משתמשים בתור ובמחסנית. באיזה סוג חיפוש משתמשים בתור, ובאיזה למחסנית?
2. השאלה על הכפל, תוך שימוש ב inc, dec, jnz, אשר מופיעה כאן בפוסטים קודמים.
3. נתון הקוד הבא:
קוד: בחר הכל
extern short const_array[2000]
long fun(short x) {
static array[2000];
long res = 0;
for (int i=1999; i>0; i–) array[i] = array[i-1];
array[0] = x;
for (i=0; i<2000, i++) res += array[i]*const_array[i];
return res;
}
כאשר כתיבה למערך לוקחת 5 מחזורי שעון, קריאה והשמה למשתנה 5 מ"ש, וכל פעולה אחרת מ"ש אחד. ללולאת ה for עצמה איך בזבוז מ"ש.
לצורך העניין, סיבוכיות הפונקציה הנ"ל היא 23n+6 (כאשר n מייצג 2000).
המשימה: לצמצם את זמן הריצה.
אני הגעתי ל 18n, אבל המראיין אמר לי שאפשר בסדר גודל של חצי. לא הצלחתי .
המשך –
ל-traversing שהוא depth first (כלומר כל ה pre / post / in orders), צריך להשתמש במחסנית. הרעיון הוא שדוחפים ושולפים נתונים מהמחסנית בהתאם לסוג הסריקהץ
ל-traversing שהוא breadth first, משתמשים בתור (שהוא בעצם FIFO). למה זה היגיוני? תחשבו שהכנסתם לתור את האב, שני בניו, ואז 4 "נכדים". הסריקה צריך להתבצא מהאב -> בנים -> נכדים.