רוטר - אתגרון. (ריבועי קסם)

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"אתגרון. (ריבועי קסם)"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #6589	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 6589

dryice

דרג אמינות חבר זה

18:33 20.07.03

אתגרון. (ריבועי קסם)

ערכתי לאחרונה בתאריך 25.07.03 בשעה 21:47 בברכה, dryice

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

ריבוע קסם בגודל N*N הוא ריבוע בו מסדרים את כל המספרים
מ 1 עד N^2 כך שסכום כל השורות וכל העמודות שווה ושווה לסכום
כל אחד משני האלכסונים.

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
באמת הגיע הזמן להחזיר את האתגרים	hll	20.07.03 20:30	1
כתבתי משהו פעם למקרה האי-זוגי	liranr	20.07.03 21:10	2
שאלה,	דני15	20.07.03 22:34	3
לא קולטים את המספרים	yoash	21.07.03 00:08	4
אממממ כתבתי תוכנית דומה באסמבלר	cuteface	21.07.03 00:57	5
ענק חחחח היה לי את זה במבחן בסי	no_angel	21.07.03 01:55	6
לעבור על כל הסידורים זה לא ממש סביר.	dryice	21.07.03 12:31	7
בהנחה שקיים ריבוע כזה	szargel	21.07.03 15:12	8
אוקי, עידכון	liranr	23.07.03 20:49	9
יש לי פתרונות היוריסטים כלליים	dryice	24.07.03 15:15	10
אז ככה	liranr	24.07.03 15:24	11
לא אמרתי שצריך, להיפך	dryice	24.07.03 15:53	12
נשמע מעניין	liranr	24.07.03 16:00	13

hll

דרג אמינות חבר זה

20:30 20.07.03

1. באמת הגיע הזמן להחזיר את האתגרים
בתגובה להודעה מספר 0

סופסוף!
חוצמזה גם למתחילים (כמוני) לא יזיקו חיות יותר קלות...

בקשר לחידה
אין לי תשובה :-|

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

21:10 20.07.03

2. כתבתי משהו פעם למקרה האי-זוגי
בתגובה להודעה מספר 0

שזה המקרה הפשוט יותר (למיטב ידיעתי), אבל אני כרגע לא מוצא את זה.
אם יהיה לי זמן (אני כרגע עסוק בקורס המרתק "תורת החבורות") אני יכתוב משהו
כללי יותר.
בכל מקרה, כל החומר המתמטי הדרוש מופיע כאן:
http://mathworld.wolfram.com/MagicSquare.html

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

דני15
חבר מתאריך 3.8.02
47437 הודעות, 8 פידבק, -3 נקודות

22:34 20.07.03

3. שאלה,
בתגובה להודעה מספר 0

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

yoash

דרג אמינות חבר זה

00:08 21.07.03

4. לא קולטים את המספרים
בתגובה להודעה מספר 3

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

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

מקווה שאני בכיוון הנכון פשוט אני גמור מעייפות אז לא תרגמתי את הרעיון לקוד בC.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cuteface

דרג אמינות חבר זה

00:57 21.07.03

5. אממממ כתבתי תוכנית דומה באסמבלר
בתגובה להודעה מספר 4

בפרויקט לבגרות שלי,
אני אנסה לערוך את זה קצת ואכניס את זה פה

חחחח זה הולך להיות מגעיל, אני לא ממאין שאני נוגע בשפה הזו אחרי הבגרות...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

no_angel
חבר מתאריך 20.3.02
4989 הודעות, דרג אמינות חבר זה

01:55 21.07.03

6. ענק חחחח היה לי את זה במבחן בסי
בתגובה להודעה מספר 5

האחרון .
זה משנה אם השיטה יעילה או לא?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

12:31 21.07.03

7. לעבור על כל הסידורים זה לא ממש סביר.
בתגובה להודעה מספר 4

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

szargel

דרג אמינות חבר זה

15:12 21.07.03

8. בהנחה שקיים ריבוע כזה
בתגובה להודעה מספר 7

עם מספרים חד ספרתיים, יש לנו 10 בחזקת 81 אפשרויות...
אני לא רוצה לחשוב מה קורה אם צריך לחשב את זה עם מספרים דו או תלת-ספרתיים....

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

20:49 23.07.03

9. אוקי, עידכון
בתגובה להודעה מספר 0

כתבתי משהו שעובד כאשר n mod 4 <> 2.
אני עדיין תקוע במקרה שבו n=4k+2, למישהו יש אלגוריתם "נחמד" שיעזור לי?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

15:15 24.07.03

10. יש לי פתרונות היוריסטים כלליים
בתגובה להודעה מספר 9

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

15:24 24.07.03

11. אז ככה
בתגובה להודעה מספר 10

דבר ראשון שאלה טיפשית: בשביל מה לפתח אלגוריתמים היוריסטים?
הפתרונות "שלי" (למקרה האי-זוגי והמתחלק ב-4) עובדים מצויין בסיבוכיות
(O(n². בהתחשב בעובדה שחייבים לעבור על כל תא בריבוע פעם אחת לפחות, זוהי
הסיבוכיות המינימלית.

האלגוריתמים של הפתרונות לא שלי, אלא מצאתי אותם בנבירה ברשת (בעיקר
באתר המצוין של mathworld שנתתי אליו לינק בהודעה קודמת). אין לי הוכחה
לנכונותם, אבל הבנתי שהוכחה כזאת קיימת:
http://rotter.net/User_files/nor/3f1fd0000ccda2dd.txt
לא יודע כמה יפה זה כתוב, אבל זה עובד

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

15:53 24.07.03

12. לא אמרתי שצריך, להיפך
בתגובה להודעה מספר 11

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

16:00 24.07.03

13. נשמע מעניין
בתגובה להודעה מספר 12

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד