פורסם 2002 בדצמבר 2922 שנים לפני זמן קצר נתנו לנו, הסטודנטים בקורס מבוא למדעי המחשב באונ' חיפה עבודת בית מאד מעניינת - למצוא מרחק עריכה בין שתי מלים. מרחק עריכה הוא הכמות המינימאלית של פעולות אלמנטריות שצריך לעשות בכדי להגיע ממחרוזת אחת לשניה. פעולות אלמנטריות הן החלפת תו בתו אחר, מחיקת תו והוספת תו חדש (insert) במקום מסויים במחרוזת תוך הזזת שאר התוים אחריו קדימה. הנה פונקציה edit_distance שמחשבת מרחק עריכה הין שתי מלים (הפתרון של שעורי הבית שלנו :): #include <stdio.h>#include <stdlib.h>int min3(int a, int b, int c){ if (a<=b && a<=c) { return a; } else if (b<=a && b<=c) { return b; } else if (c<=a && c<=b) { return c; } else { printf("BUG!\n"); exit(EXIT_FAILURE); }}int edit_distance(char *word1, char *word2){ int *D, len1, len2, i, j, p; len1 = strlen(word1); len2 = strlen(word2); p=(len1+1)*(len2+1)*sizeof(int); if (NULL==(D=(int *)malloc(p))) { printf("Not enough memory!\n."); exit(EXIT_FAILURE); } for(i=0;i<=len1;i++) { D[i]=i; /* d[i,0]=i; */ } for(i=0;i<=len2;i++) { D[i*(len1+1)]=i; } for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { p=!(word1[i-1]==word2[j-1]); D[j*(len1+1)+i]=min3(D[(j-1)*(len1+1)+(i-1)]+p, D[j*(len1+1)+(i-1)]+1, D[(j-1)*(len1+1)+i]+1); } } p=D[len2*(len1+1)+len1]; free(D); return p;} אם אתם רוצים, אני גם אעלה את האלגוריתם (שמוגדר בצורה רקורסיבית, אבל באמצעות "תכנות דינאמי" תורגם לאלגוריתם איטרטיבי שמשתמש במערך).
פורסם 2002 בדצמבר 3122 שנים משהו פרקטי? לקבל 100 במבחן בתכלס אני בתור סטונדט בטכניון הבנתי כבר שמה שאנחנו עושים לא ישמש אותנו אף פעם התרגיל מיועד רק בשביל לבדוק ידע בתכנות (רקורסיה וכו) וחשיבה טובה על אלגורתמים וסתם להעשרה אני לומד על מעבד MIPS שמת כבר לפני איזה 10 שנה אני לומד אסמבלר של PDP-11 שמת לפני 10 שנה מה שחשוב זה העקרונות ולא השימוש
פורסם 2002 בדצמבר 3122 שנים זה לא נכון לדבר על שפות מתות! Cobol שמת לפני 10 שנה לדוגמא (זה השפה השנייה בעתיקותה אחרי Fortran), אז רוב מערכות המחשוב של בנק הפועלים מבוססות עליו...
פורסם 2002 בדצמבר 3122 שנים ועוד משהו ליידע כללי:PDP-11 נקרא "מיני-מכונה" בגלל שהוא תפס שטח בגודל של רק ארון! (כל השאר היו הרבה יותר גדולים...)
פורסם 2002 בדצמבר 3122 שנים מחבר מישהו יכול לתת לי דוגמא למשהו פרקטי שמשתמשים בזה? ל-Word יש מילון של מלים, ואם הוא מוצא מילה שגויה, הוא מציע מילים "קרובות" אל המילה השגויה כאפשרויות לתיקון. מילה קרובה למילה X היא מילה עם מרחק עריכה נמוך מהמילה X.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.