מציג תוצאות 1 עד 7 מתוך 7

אשכול: שאלת ריצוף

  1. #1
    הסמל האישי שלletisya800 משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל שאלת ריצוף

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

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

  2. #2
    משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל

    315

  3. #3
    הסמל האישי שלletisya800 משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    דרך?
    נערך לאחרונה על ידי אריאל, 18-12-2018 בשעה 07:35

  4. #4
    משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל

    פשוט עברתי על כל האופציות, למען האמת נתתי למחשב לעשות את זה בשבילי:
    אני די בטוח שבעיות מהסגנון הזה נקראות בעיות אופטימזציה, יש שיטות יותר טובות לעשות את זה.
    (אמליץ לך לקרוא על בעיית המטבעות אם זה מעניין אותך)
    קוד:
    #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$
    נערך לאחרונה על ידי אריאל, 18-12-2018 בשעה 07:36
    אהבתי letisya800 אהב \ אהבו את התגובה
     

  5. #5
    אסיסטנט חבר Emath בכיר

    פרטי משתמש

    ברירת מחדל

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

  6. #6
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    זה ניסוח של בעיית פורביניו עבור $n=3$. במקרה הכללי, לא ידוע על אלגוריתם שפותר את הבעיה בסיבוכיות קבועה. כלומר, אין נניח איזו דרך עם מספר פעולות סופי שקובע מה האורך שלא תוכל לרצף. ובכל זאת, בגלל שאנחנו חסומים לאורך 1000 לכל היותר, ניתן לפתור את הבעיה בסיבוכיות קבועה (אבל עם מספר פעולות לא קטן במיוחד, ושימוש בקצת זיכרון). הפתרון הזה מסתמך על "תכנות דינמי".
    בצורה טיפה יותר פורמלית אומרים שהסיבוכיות זמן ומקום של האלגוריתם היא $O(N)$ כאשר $N$ הוא הגבול העליון (במקרה שלנו $N=1000$, אז הסיבוכיות קבועה). בסוף אני אציין איך אפשר לשפר טיפה את האלגוריתם (סיבוכיות הזמן תשאר זהה במקרה האסימפטוטי, אבל את סיבוכיות המקום ניתן לשפר ל-$O(k)$ כאשר $k$ האורך של הלבנה הארוכה ביותר).

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

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


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

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

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

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

    כמו שאבישי רשם, התוצאה המתקבלת היא באמת 229.
    נערך לאחרונה על ידי Yes, 22-12-2018 בשעה 20:42
    אהבתי אריאל, letisya800, ThePrince אהב \ אהבו את התגובה
     

  7. #7
    הסמל האישי שלletisya800 משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    הסבר מתמטי יכול להיות נהדר, תודה רבה!

מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 0

There are no members to list at the moment.

הרשאות

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

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו