שתי שאלות לא חכמות במיוחד

[אמיתי ר]

שתי שאלות לא חכמות במיוחד

למרות שתמיד אמרו לי שאין שאלות טיפשיות, יש רק אנשים טיפשים

אשמח לסיוע: הראשונה פשוטה, ואיננה ממש חלק מתרגיל שאני צריך להגיש: האם יש דרך, בהינתן מספר עשרוני, להמירו לבסיס 4 (אני קצת מפשט את דרישותי), אולם כך שזה יעשה באמצעות חישוב פשוט והתוצאה גם כן תהיה "כביכול" עשרונית. דוגמה: המספר העשרוני 7. ייצוגו בבסיס 4, יהיה 13. אני רוצה להגיע לתוצאה 13, באמצעות חישוב מתמטי, כך שהמחשב יראה ב"13" מספר כביכול עשרוני, ולא כ "3" ו"1". שאלה יותר מסובכת, הלקוחה ממ"ן שאני צריך להגיש, אז אשמח רק לכיוון/רמז: בהינתן גרף מכוון בו כל קשת צבועה באדום או שחור. האם קיימת בגרף תת-קבוצה של צמתים כך שלכל צומת יש גם קשת יוצאת אדומה (לפחות אחת) וגם קשת יוצאת שחורה (לפחות אחת). תודה!

 

[אמיתי ר]

הכיוון שלי

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

 

[לומדת74]

בנושא הבסיסים...

ההמרה בין הבסיסים מתבצעת לוגית. מכיוון שבבסיס 4 כל 4 מספרים הופכים להיות 10, ואז 4 עשיריות הופכות להיות 100.... 1. יש את הדרך המאד אינטואטיבית אך לא יעילה, של לרוץ מ1 עד המספר שלך, ולקיים מונה בבסיס 4. אפשר לעשות את זה למשל בעזרת מערך של מספרים, כאשר הראשון במערך מייצג את האחדות, השני את העשרות וכו. כל פעם שמעלים באחד, אם הספרה היא 3, מאפסים אותה ומעלים את הבא באחד. וכן הלאה. כמובן שזו שיטה מאד לא יעילה. אבל קל לשלוף את המספר מהמערך אח"כ. כי אתה בעצם הולך ומכפיל את מספר התא ב10 בחזקת המספר. (כך למשל המספר השלישי שהוא עם INDEX של [2], יהיה 10 בריבוע כפול המספר שכתוב שם)... 2. השיטה השנייה, היא משהו שמצאתי הרגע, בחיפוש אחר רעיון, אם היא נכונה, היא בטח מוכרת. אתה מחלק את המספר שלך שוב ושוב בבסיס החדש. עד שמתקבל מספר שהחלק השלם שלו קטן מהבסיס. למשל אם אתה רוצה לבדוק את 100 בבסיס 8, תחלק אותו ב8 פעמיים. תקבל 1.5625. עכשיו קח רק את מה שמשמאל לנקודה. כלומר את ה1. תרשום אותו בצד ותכפיל את היתר (0.5625) ב8 בחזרה. תקבל 4.5. שוב, קח רק מה שמשמאל לנקודה, שזה 4. ותכפיל את היתר (0.5) ב8. תקבל 4. התוצאה היא 144. בדקתי את זה על שני מספרים וזה נראה עובד. אני ממליצה לך לבדוק על עוד. בהצלחה. בקשב לשאלה השנייה, אני לא זוכרת גרפים מספיק טוב.

 

[אמיתי ר]

בהחלט, השיטה השניה

מוכרת וידוע, פשוט, היא קלה לחישוב ידני, אבל לתוכנת מחשב, אני בעצם צריך להשתמש ב MOD/DIV, הכפלה כל פעם ב-10 בחזקת מונה כלשהו. שזה קל ונוח בשפת תכנות פרוצודורלית רגילה, אבל אני רוצה ליישם את החישוב בתוך פרולוג, שמאוד מקשה על הנושא. כמובן שאם לא אמצא דרך טובה יותר, אכן אממש בעזרת האלגוריתם הזה, אבל סתם חשבתי אולי מישהו מכיר דרך יותר "קלה" לחישוב (מעין "נוסחאת פלא", כמו שיש לדוגמה, בהמרה בין בסיסים שונים לוגריתמים)

 

[אמיתי ר]

אה, ו../images/Emo51.gif ../images/Emo13.gif

 

[Fingertip]

הנה פתרון לשאלת הגרפים.

אני מניח שהכוונה הייתה לתת גרף, ולא סתם תת קבוצה... נעבור על הגרף בצורה הבאה: נשמור מבנה נתונים S המכיל אוסף של צמתים, ונבצע עליו את האלגוריתם הבא: 1) הכנס ל-S את כל הצמתים בגרף. 2) כל עוד S אינו ריק, בצע: 2.1) הוצא מ-S צומת v. 2.2) אם ל-v אין קשת יוצאת אדומה או שאין לה קשת יוצאת שחורה: 2.2.1) הכנס ל-S את כל הצמתים שיצא מהם חץ אל v. 2.2.2) מחק את v מהגרף. אני משאיר לך להוכיח למה האלגוריתם הבא עובד ולחשב את הסיבוכיות. כמו-כן, לא בדקתי עד כמה הוא יעיל... אהד.

 

[Fingertip]

כמובן ששכחתי את שלב 3

3) אם נשארו צמתים בגרף, אזי הצמתים הנ"ל מהווים את תת הגרף הדרוש. אחרת, אין תת גרף כדרוש. אהד.

 

[אמיתי ר]

אתה איש מרושע

ביקשתי רמז! כיוון! לא פתרון. אוף עכשיו הרסתי לי... אבל המון המון המון תודה

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

 

[Fingertip]

../images/Emo26.gif

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

 

[אמיתי ר]

כמובן צחקתי ../images/Emo13.gif

לא התכוונתי ברצינות שאתה מרושע..

עזרת מאוד (למרות שכאמור, נדמה לי כעת שזה לא עומד בסיבוכיות הזמן הנדרשת... )

 

[אמיתי ר]

../images/Emo93.gif קבל ביטול

מסתבר שהאלגו' צריך להיות בסיבוכיות זמן לינארית למספר צמתים/קשתות. והאלגו' שהצעת חסום, להבנתי ב O(E*V) אוף Back to the drawing board

 

[אמיתי ר]

למישהו יש רעיונות נוספים?

SOME ONE? |חושב|

 

[johnny d]

כן

בהינתן מספר (מתמטי!, כך שלא מעניין אותי יצוגו כל עוד ניתן לבצע עליו פעולות חשבון) יש אלגוריתם פשוט לביצוע התהליך שאתה מעוניין לבצע. נניח כי אתה רוצה לקבל מספר y בבסיס b עם ספרות רק מבסיס a כך שספרות אלו מייצגות את המספר x בבסיס a. כל מה שאתה צריך לעזות זה להריץ את האלגוריתם הבא: פשוט תעתיק למקום בו ניתן להבין מה רשמתי, אלו שני פונקציות השניה רקורסיבית trans(x) - return trans_ab(x, 1) trans_ab( x, n ) - if x = 0 then return 0 - trans_ab( x div a, n * b) + (x mod a) * n

 

[johnny d]

אה וגם לזה כן

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

 

[אמיתי ר]

לא...

כנראה לא הבנת את השאלה, אבל תודה בכל מקרה, מצאתי אלגוריתם אם מישהו ארצה אכתוב אותו מחר-מחרתיים אחרי שאסיים סופית. לגבי בסיסי הספירה - תודה. "תרגמתי" משהו דומה באמת לפרולוג ועובד מצוין