PDA

צפה בגרסה המלאה : שאלת ריצוף



letisya800
17-12-2018, 13:18
מעצב רצפות החליט לרצף בכניסה לארמון פס של אריחים (מסודרים אחד אחרי השני) אשר אורכו לא יעלה על 1,000 ס"מ.
לרשותו של המעצב נתונים אריחים משלושה סוגים שונים: אריחים באורך 23 ס"מ, אריחים באורך 27 ס"מ ואריחים באורך 36 ס"מ.
מכל סוג נתון מספר בלתי מוגבל של אריחים. אין לחתוך אריחים לחלקים. תחת מגבלה זו, לא ניתן לרצף כל אורך שירצה המעצב.
לכן, למשל, ניתן לרצף אורך של 100 ס"מ (על ידי שני אריחים באורך 23 ס"מ ועוד שני אריחים באורך 27 ס"מ). ניתן לרצף אורך של 109 ס"מ, וגם אורך של 700 ס"מ; אך אין דרך לרצף אורך של 70 ס"מ או אורך של - ס"מ.

מהו האורך הגדול ביותר של (שאינו עולה על 1000, ס"מ) אשר לא ניתן לרצף עם סוגי אריחים הנתונים?

ThePrince
17-12-2018, 17:59
315

letisya800
17-12-2018, 20:29
דרך?:question:

ThePrince
17-12-2018, 20:45
פשוט עברתי על כל האופציות, למען האמת נתתי למחשב לעשות את זה בשבילי:
אני די בטוח שבעיות מהסגנון הזה נקראות בעיות אופטימזציה, יש שיטות יותר טובות לעשות את זה.
(אמליץ לך לקרוא על בעיית המטבעות אם זה מעניין אותך)



#include <iostream>

using namespace std;


int main()
{
int max = 0;
int arr [1000] = {0};
for (int i=1; i<=1000/23 +1; i++)
{
for(int j=1; j<=1000/27 +1; j++)
{
for(int k=1; k <=1000/36 +1; k++)
{
int sum = 23*i+27*j+36*k;
if (sum < 1000)
arr[sum]=1;
}
}
}
for(int i=999; i>=0; i--)
{
if(arr[i] == 0)
{
cout << i << endl;
return 0;
}
}
return 1;
}

- - - - - - הודעה נוספת - - - - - -

לא הבנתי למה ציירת את הגרף של $x^2$

avishay12456
20-12-2018, 22:52
האמת היא שניתן לרצף באורך 315 ע"י 8 אריחים של 36 ו-1 של 27.
שים לב שלא חייבים להשתמש בכל סוג של אריח, ולכן כל משתני הלולאות צריכים להתחיל מ-0 ולא מ-1.
התשובה היא 229. בע"ה אם יהיה לי זמן בבוקר אצרף הסבר מתמטי.

Yes
21-12-2018, 14:43
זה ניסוח של בעיית פורביניו (https://en.wikipedia.org/wiki/Coin_problem) עבור $n=3$. במקרה הכללי, לא ידוע על אלגוריתם שפותר את הבעיה בסיבוכיות קבועה. כלומר, אין נניח איזו דרך עם מספר פעולות סופי שקובע מה האורך שלא תוכל לרצף. ובכל זאת, בגלל שאנחנו חסומים לאורך 1000 לכל היותר, ניתן לפתור את הבעיה בסיבוכיות קבועה (אבל עם מספר פעולות לא קטן במיוחד, ושימוש בקצת זיכרון). הפתרון הזה מסתמך על "תכנות דינמי (https://en.wikipedia.org/wiki/Dynamic_programming)".
בצורה טיפה יותר פורמלית אומרים שהסיבוכיות זמן ומקום של האלגוריתם היא $O(N)$ כאשר $N$ הוא הגבול העליון (במקרה שלנו $N=1000$, אז הסיבוכיות קבועה). בסוף אני אציין איך אפשר לשפר טיפה את האלגוריתם (סיבוכיות הזמן תשאר זהה במקרה האסימפטוטי, אבל את סיבוכיות המקום ניתן לשפר ל-$O(k)$ כאשר $k$ האורך של הלבנה הארוכה ביותר).

ניסוח בעברית של האלגוריתם:

אתחול: מערך $A$ בגודל 1001 שכל ערכיו 0 פרט למקומות 23, 27, 36 שם הוא 1. משתנה $\text{max}\leftarrow 0$. משתנה עזר $i\leftarrow 37$.
כל עוד $i$ קטן מ-1001, בצע:

$A[i] \leftarrow A[i-23]+A[i-27]+A[i-36]$.
אם $A[i]=0$, בצע $\text{max} \leftarrow i$.
$i \leftarrow i+1$.


החזר את $\text{max}$.


הנה דוגמה לקוד פייתון שמממש אותו:
45690



או קוד C אם את מעדיפה:
45691



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

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

כמו שאבישי רשם, התוצאה המתקבלת היא באמת 229.

letisya800
22-12-2018, 16:54
הסבר מתמטי יכול להיות נהדר, תודה רבה!