toxigun פורסם 2002 בדצמבר 29 Share פורסם 2002 בדצמבר 29 לפני זמן קצר נתנו לנו, הסטודנטים בקורס מבוא למדעי המחשב באונ' חיפה עבודת בית מאד מעניינת - למצוא מרחק עריכה בין שתי מלים. מרחק עריכה הוא הכמות המינימאלית של פעולות אלמנטריות שצריך לעשות בכדי להגיע ממחרוזת אחת לשניה. פעולות אלמנטריות הן החלפת תו בתו אחר, מחיקת תו והוספת תו חדש (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;} אם אתם רוצים, אני גם אעלה את האלגוריתם (שמוגדר בצורה רקורסיבית, אבל באמצעות "תכנות דינאמי" תורגם לאלגוריתם איטרטיבי שמשתמש במערך). קישור לתוכן שתף באתרים אחרים More sharing options...
Ewingum פורסם 2002 בדצמבר 31 Share פורסם 2002 בדצמבר 31 מישהו יכול לתת לי דוגמא למשהו פרקטי שמשתמשים בזה? קישור לתוכן שתף באתרים אחרים More sharing options...
Holy פורסם 2002 בדצמבר 31 Share פורסם 2002 בדצמבר 31 משהו פרקטי? לקבל 100 במבחן בתכלס אני בתור סטונדט בטכניון הבנתי כבר שמה שאנחנו עושים לא ישמש אותנו אף פעם התרגיל מיועד רק בשביל לבדוק ידע בתכנות (רקורסיה וכו) וחשיבה טובה על אלגורתמים וסתם להעשרה אני לומד על מעבד MIPS שמת כבר לפני איזה 10 שנה אני לומד אסמבלר של PDP-11 שמת לפני 10 שנה מה שחשוב זה העקרונות ולא השימוש קישור לתוכן שתף באתרים אחרים More sharing options...
Asystole פורסם 2002 בדצמבר 31 Share פורסם 2002 בדצמבר 31 זה לא נכון לדבר על שפות מתות! Cobol שמת לפני 10 שנה לדוגמא (זה השפה השנייה בעתיקותה אחרי Fortran), אז רוב מערכות המחשוב של בנק הפועלים מבוססות עליו... קישור לתוכן שתף באתרים אחרים More sharing options...
Holy פורסם 2002 בדצמבר 31 Share פורסם 2002 בדצמבר 31 חחחחחחחחח אהבתי PDP-11 זה מחשב שלוקח חדר סתם לידע כללי קישור לתוכן שתף באתרים אחרים More sharing options...
Asystole פורסם 2002 בדצמבר 31 Share פורסם 2002 בדצמבר 31 Cobol לוקח בניין שלם...גם ליידע כללי... קישור לתוכן שתף באתרים אחרים More sharing options...
Asystole פורסם 2002 בדצמבר 31 Share פורסם 2002 בדצמבר 31 ועוד משהו ליידע כללי:PDP-11 נקרא "מיני-מכונה" בגלל שהוא תפס שטח בגודל של רק ארון! (כל השאר היו הרבה יותר גדולים...) קישור לתוכן שתף באתרים אחרים More sharing options...
toxigun פורסם 2002 בדצמבר 31 מחבר Share פורסם 2002 בדצמבר 31 מישהו יכול לתת לי דוגמא למשהו פרקטי שמשתמשים בזה? ל-Word יש מילון של מלים, ואם הוא מוצא מילה שגויה, הוא מציע מילים "קרובות" אל המילה השגויה כאפשרויות לתיקון. מילה קרובה למילה X היא מילה עם מרחק עריכה נמוך מהמילה X. קישור לתוכן שתף באתרים אחרים More sharing options...
Recommended Posts
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.