רוטר - |חידה| מספרים מוחבאים ומכפלה סקלרית. (פתרון)

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

"|חידה| מספרים מוחבאים ומכפלה סקלרית. (פתרון)"

גירסת הדפסה

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

אשכול מספר 15998

Deuce
חבר מתאריך 1.9.08
6225 הודעות

02:10 21.07.10

|חידה| מספרים מוחבאים ומכפלה סקלרית. (פתרון)

ערכתי לאחרונה בתאריך 20.08.10 בשעה 05:03 בברכה, Deuce

פתרון החידה:
מי שרוצה, החידה נמצאת בתחתית ההודעה והוא מוזמן פשוט לדלג על הפתרון.
אני אפרסם 2 פתרונות שהגיתי, אחד מהם נפתר ע"י ג'וני הקטן השפיץ. בכנות מוזר לי נורא שהוא היחידי שפתר אבל ניחא.
תזכורת מהירה של החידה:
יש לנו וקטור של מספרים טבעיים v = a1, ... , an שאיננו יודעים את רכיביו. נתונה לנו פונקצייה שבהנתן וקטור u מחזירה את המכפלה הסקלרית uv = a1u1 + ... + anvn.
בכמה קריאות לפונקציה אפשר לגלות את הוקטור v?
פתרון א'
נשים לב כי אם התחום היה מוגבל לספרות 0-9 אז היינו יכולים לקרוא לפונקצייה עם חזקות של 10, כלומר עם וקטור שרכיביו הם 10 בחזקת i. כפלט היינו מקבלים:

a1 + 10a2 + 100a3 + ... + 10^(n-1)an

מכיוון שכל מספר הוא ספרה היינו למעשה מקבלים מספר עם n ספרות שכל ספרה מייצגת את המספר המבוקש.
נכליל את זה עתה לתחום טבעי - ראשית נקרא לפונקציה עם וקטור אחדות כדי לקבל את הסכום a1 + ... + an שגדול שווה לכל אחד מהמספרים, נסמנו ב-MAX v. כדי לבדוק כמה ספרות דצימליות תופס MAX v נעשה עליו log לפי בסיס 10 ונעגל למעלה, נקרא לתוצאה M - מספר הספרות שמספיק כדי לייצג כל מספר ai.
נשים לב כי אם נקרא לפונקציית הקסם עם הוקטור:
u = [ (10^M) , (10^M)^2 , ... , (10^M)^(n) ]

למעשה נקבל מספר שמחולק ל-Mיות באופן שה-Mיה ה-iית תייצג את ai.
תשימו לב שכל מספר תופס לא יותר מ-M ספרות, ולכן כל פעם אני כופל את המספר ב-10 בחזקה מתאימה כדי להזיז אותו.
סך הקריאות - 2.
פתרון ב'
ראשית נשתמש במשפט אלמנטרי לפיו כל מספר טבעי גדול מ-1 ניתן לייצג כמכפלה יחידה של מספרים ראשוניים, לדוגמא:
32 = 2^5; 30 = 3 * 5

אם כן, נמצא ראשית n מספרים ראשוניים, נניח ניקח את n הראשוניים השונים, כלומר:

p1 = 2; p2 = 3; p3 = 5; p4 = 7; ...

(אין לי נוסחא לראשוני ה-nי)
אם אני אצליח להחזיר ליד שלי את המכפלה:
p1^a1 * ... * pn^an = N
אז אני אוכל לגלות את ai (אני פשוט אחלק את N ב-ai עד שאקבל מספר לא שלם, מספר הפעמים שיכולתי לחלק את N ב-ai מסומן ב-ord pi ושווה פשוט ל-ai).
(עכשיו נשתמש ב"מתמטיקה" או יותר נכון בחוקי לוגים בסיסיים, אז תחזיקו אצבעות)
נשלח לפונקציה את:

v = (log p1, ... , log pn)
and lets do the math:
a1log p1 + ... + anlog pn = log (p1^a1) + ... + log (pn^an) =
= log (p1^a1 * ... * pn^an)

כלומר הפלא ופלא - הפונקציה מחזירה לנו את log המכפלה, כלומר אם נבצע exp על התוצאה אז נקבל את N כנדרש ומשם הדרך היא קלה.
סך הקריאות - 1.

בחידה זו לא התייחסתי לאלמנטים המעשיים (למשל העובדה שיכולים לחזור לי תוצאות יחסית מאוד גדולות; בטח שאני מפעיל exp על ה-log אני עלול לקבל מספר עצום), אבל זאת לא המטרה.
מקווה שנהנתם.
יש מערך עם n מספרים טבעיים, לצערנו אבדו המספרים ואנחנו לא יודעים אף מספר מאיברי המערך ! רצה הגורל וסידר לנו פעולת קסמים magicScalarProduct, המקבלת כקלט וקטור V עם n מספרים ממשיים ומחזירה את המכפלה הסקלרית של הוקטור V עם אברי המערך. כלומר, נניח שאברי המערך מיוצגים ע"י וקטור:

u = (a1,...,an)

אז פונקציית הקסם שלנו תחזור לנו את:

v*u = v1*a1 + ... + vn*an

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

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
מכתב	ronen333	21.07.10 09:50	1
הוא לא אמר שהמערך מוגבל ל0 עד 9:S	akoka2	21.07.10 11:34	2
אני לא דיברתי על אורך המערך אני דיברתי על ספרה.	ronen333	21.07.10 18:53	6
מכתב	Deuce	21.07.10 18:24	4
ממ כן	ronen333	21.07.10 18:56	7
חשבתי קצת על הפתרון,	akoka2	21.07.10 18:23	3
זה אכן פתרון אפשרי.	Deuce	21.07.10 18:25	5
למה תמיד מסתבכים עם החידות שלי...	Deuce	31.07.10 20:02	8
חח, מאיפה החידה הזו?	Sn00py	01.08.10 06:02	9
חח הוא פתר אותה בקריאה אחת :O	akoka2	01.08.10 10:49	10
וואלה? מספרים אותה בהרבה מקומות אם כך.	Deuce	01.08.10 15:27	13
טוב דיי התחרפנתי חח תביא פתרון ^^	ג'וני הקטן	01.08.10 13:13	11
דווקא אתה קרוב:)	akoka2	01.08.10 14:00	12
יש כיוון עם מספרים ראשוניים, אבל הוא יחסית קשה.	Deuce	01.08.10 15:29	14
יש לכם עד הסופ''ש.	Deuce	16.08.10 00:32	15
אה שחכתי מזה... אני ינסה לשבור קצת את הראש עוד מחר	ג'וני הקטן	16.08.10 00:38	16
מכתב	Deuce	16.08.10 01:02	17
כן אני יודע...	ג'וני הקטן	16.08.10 01:10	18
רמז.	Deuce	17.08.10 00:55	19
חשבתי על זה בדיוק אתמול בלילה חח	ג'וני הקטן	17.08.10 01:40	20
נו אז תכליל את זה עבור מספרים טבעיים כלשהם.	Deuce	17.08.10 01:41	21
חחח אתה רומז לי שאני במרחק נגיעה מהפתרון	ג'וני הקטן	17.08.10 01:52	22
טוב פתרתי... אבל אני מאמין שלא זה מה שהתכוונת חח	ג'וני הקטן	17.08.10 02:32	23
זה דווקא אחד הפתרונות :)	Deuce	17.08.10 13:30	24
תודה :) אני ימשיך לחשוב על המספרים הראשוניים :)	ג'וני הקטן	17.08.10 13:31	25
מחוכם הפתרון השני... נהנתי :)	ג'וני הקטן	20.08.10 12:15	26
אני מצטער עכשיו שלא ניסתי להמשיך לפתור את התרגיל..אהבתי	ronen333	20.08.10 16:19	27

ronen333
חבר מתאריך 20.2.03
6069 הודעות

09:50 21.07.10

1. מכתב
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 21.07.10 בשעה 09:55 בברכה, ronen333

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

{3,2,5,1}
אז אנחנו צריכים לגלות את 4 איברים אחרים שגומרים לזה להיות התוצאה.
אז אינטואטבית נריץ עבור כל מספר לולאה מ0 עד 9. מכיוון ש0 עד 9 זה לולאה קבועה, אז אפשר להגיד שאפשר לפתור את זה בזמן ריבועי (?).
בסוף נוכל לגלות שהוקטור ה"קסם" הוא 0,6,2,0

אני צריך לזוז לעבודה.. אז אני אחשוב שם על דרך יותר טובה אם יש כזו >:

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

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

akoka2

11:34 21.07.10

2. הוא לא אמר שהמערך מוגבל ל0 עד 9:S
בתגובה להודעה מספר 1

ערכתי לאחרונה בתאריך 21.07.10 בשעה 11:47 בברכה, akoka2

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

תקרא קצת על האקסיומות.

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

18:53 21.07.10

6. אני לא דיברתי על אורך המערך אני דיברתי על ספרה.
בתגובה להודעה מספר 2

אבל לא משנה כי זה לא נכון..

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

18:24 21.07.10

4. מכתב
בתגובה להודעה מספר 1

בקריאה אחת סתמית בטוח לא תצליח לגלות.
למשוואה a1v1 + ... anvn = b כאשר b מספר ייתכנו מספר פתרונות.
לדוגמא:
a1 + a2 = 8
a1 = 4, a2 = 4
a1 = 5, a2 = 3

אתה לא יכול להסיק את הפתרון.

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

18:56 21.07.10

7. ממ כן
בתגובה להודעה מספר 4

לא יודע מה עבר עלי >:

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

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

akoka2

18:23 21.07.10

3. חשבתי קצת על הפתרון,
בתגובה להודעה מספר 0

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

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

18:25 21.07.10

5. זה אכן פתרון אפשרי.
בתגובה להודעה מספר 3

להעביר בכל איטרציה את וקטורי בסיס היחידה ולקבל בכל איטרציה את ai. מה שכן - אפשר בפחות קריאות לפונקציית הקסם לפתור (אתה פתרת ב-n קריאות כאמור).

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

20:02 31.07.10

8. למה תמיד מסתבכים עם החידות שלי...
בתגובה להודעה מספר 0

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

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

Sn00py
חבר מתאריך 1.8.02
2954 הודעות

06:02 01.08.10

9. חח, מאיפה החידה הזו?
בתגובה להודעה מספר 0

אתה יודע שהביאו לנו אותה באיזשהו שלב בקורס?

\x6C\x65\x65\x74\x68\x61\x78\x30
\x72\x3A\x2D\x29
tresp4sser

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

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

akoka2

10:49 01.08.10

10. חח הוא פתר אותה בקריאה אחת :O
בתגובה להודעה מספר 9

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

15:27 01.08.10

13. וואלה? מספרים אותה בהרבה מקומות אם כך.
בתגובה להודעה מספר 9

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

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

13:13 01.08.10

11. טוב דיי התחרפנתי חח תביא פתרון ^^
בתגובה להודעה מספר 0

ניסיתי ללכת לכיוון מספרים ראשוניים אבל אנלא מתקדם שם... בכלל :\
אוף אנלא זוכר ליניארית בשיט חח

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

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

akoka2

14:00 01.08.10

12. דווקא אתה קרוב:)
בתגובה להודעה מספר 11

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

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

15:29 01.08.10

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

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

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

00:32 16.08.10

15. יש לכם עד הסופ''ש.
בתגובה להודעה מספר 0

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

00:38 16.08.10

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

עם הכיוון של המספרים ראשוניים...
ננסה >.< הבאסה זה שאני כבר לא בראש הזה :(

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

01:02 16.08.10

17. מכתב
בתגובה להודעה מספר 16

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

לכן מומלץ

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

01:10 16.08.10

18. כן אני יודע...
בתגובה להודעה מספר 17

כבר כתבתי יותר מפעם אחת פה כמה אני מבואס שאבד לי הראש לעניינים האלה אחרי שנה של ניוון :\

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

00:55 17.08.10

19. רמז.
בתגובה להודעה מספר 0

נניח וכל מספר ai היה ספרה, כלומר מספר טבעי בין 0 ל-9 כולל.
האם אז אפשר היה לפתור במעט קריאות?

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

01:40 17.08.10

20. חשבתי על זה בדיוק אתמול בלילה חח
בתגובה להודעה מספר 19

שאז (בהנחה שאתה יודע את גודל הווקטור הסודי) אתה פשוט צריך שהווקטור מכפלה יהיה:
1,10,100,1000....

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

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

01:41 17.08.10

21. נו אז תכליל את זה עבור מספרים טבעיים כלשהם.
בתגובה להודעה מספר 20

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

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

01:52 17.08.10

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

אני מתחרפן... אתה ממש רוצה? תכניס את זה לפייטון בהנחה שהמספרים בווקטור הראשון הם INTים אתה עושה את מקסימום הספרות בINT כהפרש בין כל איבר בווקטור השני ומכניס את זה לLONG שבפייתון לא מוגבל בגודל והנה פתרון בקריאה אחת >.<

אוף טוב אני ימשיך לחשוב חחח סתם מוציא תיסכולים על עצמי חח

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

02:32 17.08.10

23. טוב פתרתי... אבל אני מאמין שלא זה מה שהתכוונת חח
בתגובה להודעה מספר 0

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

1, 1, 1...

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

1, 1000, 1000000....

חזרה אנחנו נקבל מספר דיי גדול... שכל 3 ספרות בו מייצגות מספר בווקטור הנעלם..
ההסתייגות? הגדול של המספר הזה... דיי בטוח שזה יגרום לINT OVERFLOW חח ככה שזה בטח לא הפתרון שהתכוונת אליו... אבל אנערף זרקתי רעיון...

אם זה לא זה אז תגיד ואני ימשיך לשבור ת'ראש

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

13:30 17.08.10

24. זה דווקא אחד הפתרונות :)
בתגובה להודעה מספר 23

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

בכל מקרה,
כל הכבוד !

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

13:31 17.08.10

25. תודה :) אני ימשיך לחשוב על המספרים הראשוניים :)
בתגובה להודעה מספר 24

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

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

ג'וני הקטן
חבר מתאריך 24.6.10
1166 הודעות

12:15 20.08.10

26. מחוכם הפתרון השני... נהנתי :)
בתגובה להודעה מספר 0

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

16:19 20.08.10

27. אני מצטער עכשיו שלא ניסתי להמשיך לפתור את התרגיל..אהבתי
בתגובה להודעה מספר 0

מאוד את הפתרון הראשון..

את הפתרון השני לא כל כך הבנתי X=
איבדתי אותך עוד במשפט הראשון..

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

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