מישהו יכול לעזור לי?

[smser]

מישהו יכול לעזור לי?

יש לי שני תרגילים שאני לא מצליח לעשות!אשמח לקבל עזרה! 1.נתון שני מערכים A ו-B בגודל 20 תאים המכילים מספרים שלמים מסודרים בסדר עולה ואשר בכל אחד מהם אין איברים אשר חוזרים על עצמם. כתוב תוכנית אשר תבצע את שתי הפעולות על המערכים הנ"ל: א.חיתוך-פעולה זו תיצור מערך חדש C, שאליו יכנסו כל האיברים המופיעים במערך A וגם במערך B. ב.איחוד-פעולה זו תיצור מערך חדש בשם D, שאליו יכנסו כל האיברים המופיעים במערךA או במערך B אבל לא בשניהם. גם איברי המערכים D וC צריכים להיות מסודרים בסדר עולה ואסור שהאברים יחזרו על עצמם(זה כבר לא סיפור,מיון בועות פשוט) 2.כתוב תוכנית הקולטת שתי מחרוזות ובודקת האם אפשר מאותיות המחרוזת הראשונה להרכיב את השניה. לדוגמא- עבור שתי המחרוזות "אנציקלופדיה" ו"קיצוני" התוכניס תדפיס YES אך על המחרוזות "אנציקלופדיה" ו"אינני" היא תדפיס NO תודה!

 

[ron369]

מה כבר עשית?

א) תאפיין כל איבר בתוצאה, בעזרת האיברים מ-A ו-B. כלומר, אתה צריך להגיע למצב שבו "איבר X נמצא בתוצאה, אם הוא משהו עם A, ועוד משהו עם B". אז, אתה צריך להסביר למחשב את התנאי הזה. כלומר, אתה צריך "לעבור על האיברים", ולכל אחד להסביר למחשב מתי תרצה אותו בתוצאה, ואז "להכניס" אותו לשם. עכשיו ב' נעשה בדרך דומה. 2) בדרך דומה לתרגיל 1. שים לב שההבדל הוא שעכשיו בעזרת אות אחד, אי אפשר להרכיב שתי אותיות. כלומר, עדיין צריך להתקיים שכל אות ב-B נמצאת ב-A, אבל מעבר לכך, אם ה"התאמה" בין B ל-A היא פונקציה f, אזי עכשיו הפונקציה גם חח"ע. בהצלחה.

 

[smser]

אתה יכול לפרט

או יותר טוב לכתוב את התוכנה.

 

[ron369]

אני לא רוצה

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

 

[Amitus]

לגבי השאלה השנייה

לדעתי היא ממש נחמדה.. אני יודעת...בעיות ב-C לא יכולות להיות נחמדות אבל בכל זאת.. תעשה strlen למחרוזת הראשונה ואז למחרוזת השנייה..והאורך של הראונה יהיה הלולאה הראשונה, האורך של השנייה לולאה שנייה ..תעשה לולאה מקוננת שתבדוק האם האיבר במקום ה-i במחרוזת השנייה(!)מופיע איפשהו במחרוזת הראשונה אם כן תקדם מונה, אם לא תקדם את i . ואז אם בסוף הלולאה המקוננת הערך של המונה שלך יהיה שווה ל-strlen של המחרוזת השנייה אז כן..ואם לא..אז לא אם הייתי המקומך הייתי מנסה להריץ את זה..ואם טעיתי לפחות יש לך כיוון... עמית

 

[Amitus]

אגב..

לגבי השאלה הראשונה..למקרה שאתה בכיתה י' אז רק שתדע שמיון מערכים ירד במיקוד.. (אבל אם אתה לא ב-י' אז בכל אופן בהצלחה.. )

 

[vinney]

לא לא לא

עושים את זה בO של N ומשתנה עזר בגודל קבוע

 

[Amitus]

מה??

לא הבנתי

 

[vinney]

בלי לולאות מקוננות

 

[Amitus]

עשינו פעם

בכיתה משהו כזה...והמורה כתב את זה עם לולאה מקוננת... אבל אף לא ניסיתי להריץ את מה שהוא כתב,אני אנסה מחר../:

 

[vinney]

עזבי מורה, תנסי לחשוב לבד../images/Emo13.gif

מה שהצעת זה O של N^2, אפשר לעשות את זה בכמה דרכים בהרבה פחות (כמובן הכי נמוך זה O של N כי צריך לעבור על כל האותיות לפחות פעם אחת).

 

[ron369]

כנראה לא שמת לב לאחד הנתונים,

הם ממויינים בסדר עולה, לפחות בשאלה 1. אבל ככל הנראה, ויני הניח שהנתון תקף גם לשאלה 2. מה שטכנית נשמע הגיוני, אבל, בעצם, אני לא בטוח בקשר לכך - הרי המחרוזות בדוגמא של הנתונים לא היו ממויינות, נכון? ולכן, נראה שהפתרון שלך מעולה, בפרט לכך שהוא מתעלם מהמקרה שבו במחרוזת אחת קיים תו מסויים שחוזר פעם אחת, ובשניה הוא חוזר כמה פעמים. לפי השאלה - התשובה במקרה זה צריכה להיות שלילית, בעוד שהתשובה שלך, אם אני מבין אותה נכון, מחזירה תשובה חיובית. חוץ מזה, אפשר לייעל את זה קצת. בפתרון שלך כאשר תו לא נמצא אנחנו מחכים עד הסוף, אם הבנתי את זה נכון. אבל אחרי שתו אחד לא נמצא, התשובה תשאר שלילית בכל מקרה, ונוכל פשוט להחזיר ערך שקר ישירות.

 

[vinney]

לא הנחתי כלום בפתרון שלי

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

 

[ron369]

אתה בטוח?(אולי יש נתון שלא ראיתי?)

 

[ron369]

הממ... נראה לי שהבנתי, אבל מה אם

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

 

[vinney]

זה לא משנה

גם הא"ב וגם הקידוד הם בO של 1. גם אם זה א"ב סיני בUTF128.

 

[ron369]

זה לא O(M), אם כבר?

(ונראה לי שאפשר O(lgM)) אבל אולי אני מתבלבל. מחר בבוקר בטח אני אצחק על עצמי...

 

[vinney]

M זה קבוע

גודל א"ב לא תלוי בקלט. בבוקר תקרא את זה ותשתעשע

 

[ron369]

אני חשבתי לנתח את זה במונחי M ו-N

אחרת לא כיף

אבל עדיין, ברוב השרשור הזה באמת נראה שהייתי צריך להיות "קצת" יותר מהיר

 

[Amitus]

טוב:

כתבתי את זה..הרצתי את זה..יצא מעולה..הבעיה היא שיש מצב שזה לא ה-כ-י יעיל..ואולי יש דרכים יותר טובות ויעילות.כמו שהצעתם נפטרתי מלולאה המקוננת ואכן אפשר בלעדיה... #include<stdio.h> #include<string.h> void main() { char st[6]="tapuz"; char st2[10]="amitapuzi"; int reslt,reslt2,i=0,j,k; reslt=strlen(st); reslt2=strlen(st2); for(j=0;j<reslt2;j++) { if(st==st2[j]) { k=j; while(st==st2[j]) { i++; j++; } if(j-k==reslt) { k=1; } } } if(k==1) { printf("good"); } else { printf("bad"); } }