PDA

צפה בגרסה המלאה : [דיון] לאן אני יכול להתקבל עם קב"א 55 ודפ"ר 80?



sagiftw
26-08-2010, 13:36
אלו הם הציונים שלי.

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

matan1212
26-08-2010, 16:45
לקבל למלא שאלון באינטרנט אתה בטח תקבל...ומאז זה קשור רק בעצמך....דרך אגב מה הרחבת?

sagiftw
26-08-2010, 17:00
מחשבים ופיזיקה.
אגב, מלאתי כבר את השאלות.

matan1212
26-08-2010, 17:02
מחשבים ופיזיקה.
אגב, מיליתי כבר את השאלות.


והודיעו לך שהתקבלת\אתה צריך לבוא למבחנים? מאוד קשה להתקבל לגאמ"א אבל בהצלחה לך:)

sagiftw
26-08-2010, 17:37
עוד לא זימנו אותי.

odp
26-08-2010, 17:41
אותי זימנו בתחילת כיתה י"א. לא הצלחתי לעבור את המבחנים הראשונים, אבל אני עדיין זוכר מספר שאלות מהמבחן של האלגוריתם.

matan1212
26-08-2010, 17:42
אותי זימנו בתחילת כיתה י"א. לא הצלחתי לעבור את המבחנים הראשונים, אבל אני עדיין זוכר מספר שאלות מהמבחן של האלגוריתם.


תכבד בכמה שאלות...

odp
26-08-2010, 18:02
תכבד בכמה שאלות...

חחח, ידעתי שזה יבוא מתישהוא, אבל לא ידעתי שכל-כך מהר... :biggrin:

משולש פסקל

אני אחסוך בהסברים לגביו, מי שלא יודע במה מדובר יקרא כאן (http://he.wikipedia.org/wiki/%D7%9E%D7%A9%D7%95%D7%9C%D7%A9_%D7%A4%D7%A1%D7%A7% D7%9C). בכל מקרה, צריך לכתוב פונקציה שתקבל את מקום האיבר במשולש ותחזיר את ערך האיבר. הסדר הוא מהשורות העליונות לשורות התחתונות ובתוך השורות הסדר הוא משמאל לימין, כמו שמתואר בתמונה המצורפת (http://img96.imageshack.us/img96/8355/paskal.png).

לכן,
f(1)=1
f(7)=1
f(8)=3

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

לוח השנה

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

matan1212
26-08-2010, 18:04
חחח, ידעתי שזה יבוא מתישהוא, אבל לא ידעתי שכל-כך מהר... :biggrin:

משולש פסקל

אני אחסוך בהסברים לגביו, מי שלא יודע במה מדובר יקרא כאן (http://he.wikipedia.org/wiki/%d7%9e%d7%a9%d7%95%d7%9c%d7%a9_%d7%a4%d7%a1%d7%a7% d7%9c). בכל מקרה, צריך לכתוב פונקציה שתקבל את מקום האיבר במשולש ותחזיר את ערך האיבר. הסדר הוא מהשורות העליונות לשורות התחתונות ובתוך השורות הסדר הוא משמאל לימין, כמו שמתואר בתמונה המצורפת (http://img96.imageshack.us/img96/8355/paskal.png).

לכן,
f(1)=1
f(7)=1
f(8)=3

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

לוח השנה

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


התרגיל השני לא נראה בעיה...כמה שבמחשב הזה לא מותקן c# שאני יוכל לכתוב פיתרון..אבל אני ינסה להביא אלגוריתם בעברי...בקשר למשולש פסקל יש לי רעיון..הוא ראשוני ויכול להיות שהוא לא ממש טוב

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

sagiftw
26-08-2010, 18:06
כן, אם אפשר לדעת, מה נוהגים לשאול?

Hurricane
26-08-2010, 18:22
בעבר פרסמתי את השאלות אבל אריאל מחק את האשכול.
בכל אופן, היום השאלות מפורסמות בכל רחבי האינטרנט. תגגל קצת ותמצא.

ד"א, איזה ידע יש לך בדיוק בתכנות?

matan1212
26-08-2010, 18:35
תגידו כדי לפתור את המשולש פסקל הזה..צריך יידע ברקורסיה?לא יודע אם זה עוזר אבל מצאתי שהסכום של שורה n שווה ל-2 בחזקת n פחות 1

1
1+1
1+1+2
1+1+3+3

1
2
4
8
....

odp
26-08-2010, 19:08
תגידו כדי לפתור את המשולש פסקל הזה..צריך יידע ברקורסיה?לא יודע אם זה עוזר אבל מצאתי שהסכום של שורה n שווה ל-2 בחזקת n פחות 1

1
1+1
1+1+2
1+1+3+3

1
2
4
8
....

KIS - Keep It Simple. עזוב אותך שנייה מרקורסיה. תנסה קודם למצוא דרך לבנות את משולש הפסקל בעזרת מבנה נתונים מסוים (לא אגלה לך איזה), ואז יהיה לך הרבה יותר קל.

Dmot
26-08-2010, 19:25
אני שנה ראשונה בתכנות בתיכון ^_^ לא לצחוק :wink:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void PrintMat(int[,] mat)
{
for (int i = 0; i < mat.GetLength(0); i++)
{
for (int j = 0; j < mat.GetLength(1); j++)
{
Console.Write("{0} ", mat[i, j]);
}
Console.WriteLine();
}
}
static void Pascal(int[,] mat,int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (j== 0 || j == i)
mat[i, j] = 1;
else
{
mat[i, j] = mat[i - 1, j-1]+mat[i-1,j];
}
}
}
}
static void Main()
{
int n = 0;
Console.WriteLine("Enter the n number of Pascal Triangle");
n = int.Parse(Console.ReadLine());
int[,] mat = new int[n,n];
Pascal(mat, n);
PrintMat(mat);
}
}
}


לא לצחוק :wink:

odp
26-08-2010, 19:30
:biggrin: סתם...

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

Dmot
26-08-2010, 19:32
:biggrin: סתם...

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

odp
26-08-2010, 19:34
לא מסתדר עם זה כאן ^^
תוכל להגיד לי איך לסדר את זה? (= זה עובד במחשב שלי...

תנסה לשים את זה ברגיל (לא ב-code), וכמובן ליישר לשמאל.

Dmot
26-08-2010, 19:48
קשה להעלות כאן תוכניות.
עם code בלי code.
אני מצרף תמונות של חלקי התוכנית...

odp
26-08-2010, 19:59
קשה להעלות כאן תוכניות.
עם code בלי code.
אני מצרף תמונות של חלקי התוכנית...

בסדר, אני סומך עליך (וקצת מתעצל לבדוק (ועסוק באתגר הדינמיט (http://www.net-games.co.il/online-games/Dynamite-Blast.html)) ) :biggrin:

Dmot
26-08-2010, 20:05
הבעיה שלי היא שהמשולש שלי הוא יש"ז (=
אני אנסה להעביר אותו למשולש רגיל...
אחלה אתגר, ד"א (=

odp
26-08-2010, 20:09
הבעיה שלי היא שהמשולש שלי הוא יש"ז (=
אני אנסה להעביר אותו למשולש רגיל...
אחלה אתגר, ד"א (=

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

Dmot
26-08-2010, 20:10
תודה! (=
ד"א, אחלה משחק...

Learn
26-08-2010, 20:13
חחח, ידעתי שזה יבוא מתישהוא, אבל לא ידעתי שכל-כך מהר... :biggrin:

משולש פסקל

אני אחסוך בהסברים לגביו, מי שלא יודע במה מדובר יקרא כאן (http://he.wikipedia.org/wiki/%d7%9e%d7%a9%d7%95%d7%9c%d7%a9_%d7%a4%d7%a1%d7%a7% d7%9c). בכל מקרה, צריך לכתוב פונקציה שתקבל את מקום האיבר במשולש ותחזיר את ערך האיבר. הסדר הוא מהשורות העליונות לשורות התחתונות ובתוך השורות הסדר הוא משמאל לימין, כמו שמתואר בתמונה המצורפת (http://img96.imageshack.us/img96/8355/paskal.png).

לכן,
f(1)=1
f(7)=1
f(8)=3

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

לוח השנה

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

תביא רמז לשאלה הראשונה.
לגבי השאלה השניה: לא הבנתי כל כך את השאלה מה הכוונה "נותנים לך לוח לועזי"?

odp
26-08-2010, 20:21
תביא רמז לשאלה הראשונה.
לגבי השאלה השניה: לא הבנתי כל כך את השאלה מה הכוונה "נותנים לך לוח לועזי"?

נותנים לך לוח שנה גרגוריאני - לדוגמה (http://www.rubiart.net/blog/wp-content/gallery/design/calendar.jpg) (זה מה שאתה רואה בדפי המבחן). אתה צריך לבנות פונקציה שתקבל תאריך בשנה הזאת (נגיד - 26/03) ותחזיר את היום בשבוע של תאריך זה (במקרה שלנו - חמישי).

שלחתי לך את הרמז בפרטי.

Dmot
26-08-2010, 20:40
odp,
כתבתי תוכנית (^) למשולש פסקל.
בשביל לפתור את הסעיף, אני אוכל פשוט לבנות מטריצה זהה שבמקום כל איבר במשולש פסקל יהיה לי קאוונטר. כך שהאיבר הראשון במשולש פסקל היא 1, השני 2 ועוד..
ואז, פשוט להשוות בין המטריצות? (הכוונה, לרוץ על המטריצה המכילה את המספרים, וכאשר נמצא המספר, להפנות למטריצה שמכילה את פסקל).
הרי, הן בעלי אותו מספר איברים...
עריכה: עובד לי (= אני אסמן את הפיתרון בלבן...

odp
26-08-2010, 20:45
odp,
כתבתי תוכנית (^) למשולש פסקל.
בשביל לפתור את הסעיף, אני אוכל פשוט לבנות מטריצה זהה שבמקום כל איבר במשולש פסקל יהיה לי קאוונטר. כך שהאיבר הראשון במשולש פסקל היא 1, השני 2 ועוד..
ואז, פשוט להשוות בין המטריצות? (הכוונה, לרוץ על המטריצה המכילה את המספרים, וכאשר נמצא המספר, להפנות למטריצה שמכילה את פסקל).
הרי, הן בעלי אותו מספר איברים...

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

Dmot
26-08-2010, 20:46
השם הוא אושר.
לא, אל תסתבך. תשתמש במונה כדי לדעת מתי להחזיר את הערך - תוך כדי בניית המשולש.
יותר יעיל, צודק (=
בכ"מ, העיקר שהפיתרון שלי נכון? ^^
סתם...
תודה רבה אושר! (=

Hurricane
26-08-2010, 20:52
ניתן בקלות לפתור את משולש פסקל באמצעות רקורסיה אך הדבר לא יעיל בכלל אם אתה רוצה למצוא כמה איברים ולא רק איבר אחד (וגם עבור איבר אחד זה לא יעיל, אבל שיהיה).
בכל אופן, אם כן רוצים למצוא איבר אחד, הפתרון טריוויאלי:


public static int getPascal(int row, int column) {
if (column > row)
return 0;
if (row == 1 || column == 1)
return 1;
return getPascal(row - 1, column) + getPascal(row - 1, column - 1);
}בנוסף, שימוש במטריצה יהיה בזבוז תאים בזכרון, שכן אתה משתמש בחצי מן המטריצה.
עדיף להשתמש במבנה נתונים דינאמי.

יש גם עוד דרכים כמו זה שהאיבר במקום (r,c) שווה בעצם ל:
\frac{r!}{c!(r-c)!}
כאשר השורות והעמודות מתחילות מאפס.
כך לדוגמא, במשולש:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1האיבר 6 הוא במיקום (4,2) ולא (5,3).

Learn
26-08-2010, 22:27
פתרון למשולש פסקל. השתמשתי בבינום של ניוטון (אני כתבתי) אבל אני קצת בטוח שיש לי שגיאה.

איזה מוזר זה: אני לא זוכר את הנוסחה בע"פ וכשחיפשתי אותה בגוגל הגעתי לפה: משולש פסקל « לא מדויק (http://www.gadial.net/?p=550) ועשיתי מה שהוא כתב. http://www.gadial.net/wp-content/latex/a41/a4102d8d14b0e69e69a977b25a7189d8-ffffff-000000-0.png התברר שזו טעות בעע..


import java.io.IOException;
import java.util.Scanner;


public class tests
{
static int Azeret(int n)
{
if (n==0)
return 1;
if (n==1)
return 1;
if (n==2)
return 2;
return (n * Azeret(n-1));
}

//N abouv K
static int Binom(int n, int k)
{
/* System.out.print(Azeret(k));
System.out.print("/(");
System.out.print(Azeret(n));
System.out.print("*(");
System.out.print(k);
System.out.print("-");
System.out.print(Azeret(n));
System.out.print("))");
System.out.println("=");
*/
return Azeret(n)/(Azeret(k)*Azeret((n-k)));
}

public static void main(String[] args) throws IOException
{
Scanner in = new Scanner(System.in);
//x is for the rows, y for the hamudot
int x,y,a;
x=1;y=1;
a=in.nextInt();
for(x=0;a>1;a--)
{
x++;

for(y=1;(x>y && a>1);a--)
{
// System.out.print(x);System.out.print(" ");System.out.println(y);System.out.print(" ");System.out.println(a);
y++;
}

}
// System.out.print(x);System.out.print(" ");System.out.println(y);System.out.print(" ");System.out.println(a);
System.out.println(Binom(x-1,y-1));



}

}




תיקונים? :question:

Hurricane
26-08-2010, 22:37
תבדוק כל פונקציה בנפרד. קודם תבדוק האם העצרת עובדת. אחר כך תבדוק האם הבינום עובד, ולבסוף את הפונקציה הראשית.
בכלל, הקוד שלך לא מובן... תן שמות נורמליים למשתנים ותעשה לולאות מובנות יותר...

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

Learn
26-08-2010, 22:49
תבדוק כל פונקציה בנפרד. קודם תבדוק האם העצרת עובדת. אחר כך תבדוק האם הבינום עובד, ולבסוף את הפונקציה הראשית.
בכלל, הקוד שלך לא מובן... תן שמות נורמליים למשתנים ותעשה לולאות מובנות יותר...

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

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

בקיצור,
בקטנה

:)

Hurricane
26-08-2010, 22:59
...?
אז איך אתה מצפה שהתוכנית שלך תעבוד? אתה לא כותב משחק FIFA שלם ואז בודק אם הוא עובד. אתה כותב חלקים קטנים, בודק אם הם עובדים וממשיך הלאה.

גם לבדוק האם העצרת עובדת זה לא כזה בעיה. אתה פשוט כותב:

System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(5));
System.out.println(factorial(7));או פשוט בודק מקרים שונים.

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

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

Learn
26-08-2010, 23:03
אה....
חשבתי שאתה מדבר על בדיקות יותר הדוקות.
ברור שבדקתי.
את הקוד תיקנתי (קרי' כתבתי) על סמך ניסוי וטעייה (עשיתי ניסיונות ובדקתי).
לא בדקתי את העצרת. את הבינום והראשי בדקתי..

sagiftw
27-08-2010, 01:05
עריכה ........

matan1212
27-08-2010, 01:47
חחח, ידעתי שזה יבוא מתישהוא, אבל לא ידעתי שכל-כך מהר... :biggrin:

משולש פסקל

אני אחסוך בהסברים לגביו, מי שלא יודע במה מדובר יקרא כאן (http://he.wikipedia.org/wiki/%d7%9e%d7%a9%d7%95%d7%9c%d7%a9_%d7%a4%d7%a1%d7%a7% d7%9c). בכל מקרה, צריך לכתוב פונקציה שתקבל את מקום האיבר במשולש ותחזיר את ערך האיבר. הסדר הוא מהשורות העליונות לשורות התחתונות ובתוך השורות הסדר הוא משמאל לימין, כמו שמתואר בתמונה המצורפת (http://img96.imageshack.us/img96/8355/paskal.png).

לכן,
f(1)=1
f(7)=1
f(8)=3

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

לוח השנה

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


בקשר לשאלה השניה..בלוח יש חודשים בעלי 29 חודשים..כאלה 30 וכו'.....או כולם עם אותו מס' ימים..?

ומה עם פסקל מישהו פתר או לחשוב על פיתרון?..איך אני מת להתחיל ללמוד רקורסיה...ב-2 שורות פותר תרגיל של 700 שורות...

Dmot
27-08-2010, 02:01
בקשר לשאלה השניה..בלוח יש חודשים בעלי 29 חודשים..כאלה 30 וכו'.....או כולם עם אותו מס' ימים..?

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

matan1212
27-08-2010, 02:03
אני דיי פתרתי, בצורה דיי גרועה, ובתור משולש יש"ז ...


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

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

Dmot
27-08-2010, 02:20
בזה שרק סיימת כיתה י' זה ממש טוב...בדרך כלל לפני פיתרון צריך להסביר במיילים מה עשית אחרת אין סיכוי להבין....
אלגוריתמים... תמיד שנאתי אותם (=
באופן כללי וחסר-אלגוריתמי.
הגדרתי מטריצה ריבועית שמספר השורות שלה יהיה n ומספר העמודות שלה יהיה n.
פתחתי מתודת void, שתקבל מטריצה int ומספר כלשהוא (int).
הגדרתי קאוונטר ואתחלתי אותו.
הרצתי לולאה מקוננת, בלולאה הראשונה, שi (שורה) ירוץ מ0 ועד n, ובלולאה השנייה, שj (עמודה) תרוץ מ-0 עד i, כולל i... הi וה-j עולים ב-1 כל עוד הלולאה של כל אחד נגמרת.
שאלתי אם j נמצא במקום 0 (עמודה 0) או אם j=i (שתי נקודות הקיצון), אם כן, אז התא במטריצה הוא 1.
בנוסף, שאלתי אם הקאוונטר שווה למקומו הסידורי של התא, אם לא, הקאוונטר עולה ב-1.
אחרת, התא במטריצה הוא סכומם של האיבר בשורה i-1,j והאיבר הסמוך לו, i-1,j-1.
שאלתי אם המקום הסידורי של התא שווה לקאוונטר, אם לא, הקאוונטר עולה.
כמובן שבשני המקרים, אם כן, אז היא מחזירה את האיבר במטריצה.
והלולאה ממשיכה לרוץ...

Dmot
27-08-2010, 02:38
הנה המתודה...

odp
27-08-2010, 09:07
בקשר לשאלה השניה..בלוח יש חודשים בעלי 29 חודשים..כאלה 30 וכו'.....או כולם עם אותו מס' ימים..?

ומה עם פסקל מישהו פתר או לחשוב על פיתרון?..איך אני מת להתחיל ללמוד רקורסיה...ב-2 שורות פותר תרגיל של 700 שורות...

לוח שנה סטנדרטי, שבו חודש פברואר אורך 28/29 ימים ושאר החודשים אורכים 30/31 ימים. בכל מקרה, לפחות תחשבו על הרעיון הכללי של הפתרון.

matan1212
27-08-2010, 14:43
לוח שנה סטנדרטי, שבו חודש פברואר אורך 28/29 ימים ושאר החודשים אורכים 30/31 ימים. בכל מקרה, לפחות תחשבו על הרעיון הכללי של הפתרון.

טוב רעיון שחשבתי עליו...אתה ידע איזה יום מתחיל כל חודש...ואז אתה מכניס למחשב באיזה חודש באיזה יום הוא מתחיל (יום שבת=0,ראשון=1,שני=2 וכו') ואז הוא מתחיל יום כלומר את התאריך נגיד ה-27.5 וידוע שהחודש החמישי מתחיל ביום ראשון כלומר 1...ואז אתה מחסר את 27-1 יוצא 26...ואז אתה מחבר את ה-26 ביום שמתחיל ביום ראשון כי זה חודש חמישי ואז 26+1=27 על זה אתה עושה 27%7 ואז זה שווה ל-6 כלומר יום שישי

matan1212
28-08-2010, 20:26
האמת חשבתי על שיטה נחמדה..הרי זה לוח שנה רגיל אז אפשר לדעת כמה ימים יש בכל חודש ואז אתה עושה פעולה שהיא מקבלת חודש ומחזירה כמה ימים יש באותו חודש נקרא לה numdays ולאחר מכן אתה יודע באיזה יום מתחיל החודש הראשון ואז אתה עושה ככה:

int firstday=a כאשר a זה היום הראשון של החודש הראשון (1) ואז אתה עושה בפור מ-1 עד החודש שהמשתמש כתב פחות אחד...ואז:

for(int i=1;i<month;i++
firstday=(firstday+numdays(i))%7;

ואז אתה יודע באיזה יום מתחיל החודש שהמשתמש בחר..

int thisday=(firstday+day-1)%7


ואז אם thisday=0 שבת אם 1 זה ראשון ,2 זה שני,3 זה שלישי,4 זה רביעי,5 זה חמישי ו-6 זה שישי....זה השיטה?

odp
28-08-2010, 20:30
מתן,

אין שום בעיה עם הפתרון שלך. אבל יש לי רמז לפתרון פשוט יותר - תשתמש במבנה נתונים מסויים.

Dmot
28-08-2010, 20:36
מתן,

אין שום בעיה עם הפתרון שלך. אבל יש לי רמז לפתרון פשוט יותר - תשתמש במבנה נתונים מסויים.
אולי אפשר בswitch-case?

odp
28-08-2010, 20:38
אולי אפשר בswitch-case?

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

Dmot
28-08-2010, 20:40
אהבתי. זה לא מה שהתכוונתי, אבל גם זה חוסך שורות. לך על זה...
חחחח, תודה (=
אני מסתפק מהתשובה שלי לשאלה הקודמת, אני אתן למתן את הכבוד לפתור את השנייה (=
תודה רבה רבה אשר! (=
אחלה שאלות.
אם תוכל להעלות עוד כמה, אני אשמח (=

matan1212
28-08-2010, 20:40
אולי אפשר בswitch-case?


יותר עדיף איפים לפי דעתי..פשוט switch-case לא מבין למה מלמדים את זה..זה גם לא מקצר וגם אפשר להסתדר בלעדיו!

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

odp
28-08-2010, 20:48
כרצונך.

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

matan1212
28-08-2010, 20:55
כרצונך.

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


תפנק אותה בשאלה..תן קצת להפעיל את המוח...קיצר לשאלה הקודמת (2)זה מה שהתכוונת פשוט ליצור מין לוח שנה?

odp
28-08-2010, 21:02
אני זוכר שלשאלת לוח השנה, הם נתנו רמז שנשמע בערך כך: "שימו לב איך בעזרת הגדרה פשוטה יחסית של מבנה נתונים, ניתן לפתור את השאלה בקלות".
הייתה אפשרות בחירה בשאלות (3 מתוך 5), ולכן הלכתי על משולש פסקל, הבניינים, ועוד שאלה שאני לא זוכר. חשבתי לפתור את שאלת לוח השנה כמו שאתה הצעת, אבל השאלות האחרות היו הרבה יותר אינטואיטיביות בשבילי, והפתרון שלהן היה יותר קצר.

Hurricane
28-08-2010, 21:51
הייתה עוד שאלה פשוטה - למצוא את המכנה המשותף הגדול ביותר של שני מספרים, ונתנו שם דרך רקורסיבית לפתרון (השיטה של אוקלידס).

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

לדוגמא, במקום לעשות (סתם דוגמא, זה לא C) כך:

if (mousePressed(RIGHT)) {
}
else if (mousePressed(LEFT)) {
}
else if (keyReleased(VK_A) {
}

יהיה ניתן להשתמש ב- switch. ותחשוב על משחקים שבהם יש המון הודעות (לאו דווקא עכבר ומקלדת - יציאה מהחלון, מזעור המשחק, עדכון החלון וכולי).

matan1212
28-08-2010, 22:00
אני זוכר שלשאלת לוח השנה, הם נתנו רמז שנשמע בערך כך: "שימו לב איך בעזרת הגדרה פשוטה יחסית של מבנה נתונים, ניתן לפתור את השאלה בקלות".
הייתה אפשרות בחירה בשאלות (3 מתוך 5), ולכן הלכתי על משולש פסקל, הבניינים, ועוד שאלה שאני לא זוכר. חשבתי לפתור את שאלת לוח השנה כמו שאתה הצעת, אבל השאלות האחרות היו הרבה יותר אינטואיטיביות בשבילי, והפתרון שלהן היה יותר קצר.

נראה אני יוצא מפגר אבל מה זאת אומרת "מבנה נתונים"?

ואפשר את הדרך שהם הביאו..?

sivan1233210
28-08-2010, 22:01
בס"ד

מבנה נתונים זה נראה לי כמו מחסנית או עץ בינארי וכל אלה.

matan1212
28-08-2010, 22:03
הייתה עוד שאלה פשוטה - למצוא את המכנה המשותף הגדול ביותר של שני מספרים, ונתנו שם דרך רקורסיבית לפתרון (השיטה של אוקלידס).

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

לדוגמא, במקום לעשות (סתם דוגמא, זה לא C) כך:

if (mousePressed(RIGHT)) {
}
else if (mousePressed(LEFT)) {
}
else if (keyReleased(VK_A) {
}

יהיה ניתן להשתמש ב- switch. ותחשוב על משחקים שבהם יש המון הודעות (לאו דווקא עכבר ומקלדת - יציאה מהחלון, מזעור המשחק, עדכון החלון וכולי).


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

matan1212
28-08-2010, 22:04
בס"ד

מבנה נתונים זה נראה לי כמו מחסנית או עץ בינארי וכל אלה.


ובעברית? סתם אני לא יודע עדיין מה זה מחסנית או עץ בינארי וכל אלה...

sivan1233210
28-08-2010, 22:04
בס"ד

מבנה נתונים – ויקיפדיה (http://he.wikipedia.org/wiki/%D7%9E%D7%91%D7%A0%D7%94_%D7%A0%D7%AA%D7%95%D7%A0% D7%99%D7%9D)

Hurricane
28-08-2010, 22:28
אה אז חשוב בעצם ללמוד switch...בינתיים אני לא מרגיש צורך להשתמך בה אבל אולי בעתיד..ומה זאת אומרת אי אפשר לפתור את השאלה " למצוא את המכנה המשותף הגדול ביותר של שני מספרים" בדרך רגילה?..למה זה לא בעיה לפתור את זה ופתרתי את זה גם כבר אבל לא בדרך רקורסיבית...
אתה לא חייב לפתור את התרגיל בדרך רקורסיבית...
בעצם הפתרון מסתמך על זה שמתקיים:
gcd(a,b)=gcd(a-b,b)=gcd(a,b-a)

או פתרון טריוויאלי בג'אווה:

public static int gcd(int a, int b) {
while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}

return a;
}אני לא זוכר אם הם ביקשו לפתור את זה רקורסיבית, אבל בכל אופן הנה הדרך הרקורסיבית:

public static int gcd2(int a, int b) {
if (a == b)
return a;

if (a > b)
return gcd2(a - b, b);

return gcd2(a, b - a);
}אתה גם לא חייב לולאות while, for, foreach או do while. מספיק סוג אחד של לולאות. אבל בכל אופן, המציאו כמה סוגים לשם נוחות.

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

matan1212
28-08-2010, 22:38
אתה לא חייב לפתור את התרגיל בדרך רקורסיבית...
בעצם הפתרון מסתמך על זה שמתקיים:
gcd(a,b)=gcd(a-b,b)=gcd(a,b-a)

או פתרון טריוויאלי בג'אווה:

public static int gcd(int a, int b) {
while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}

return a;
}אני לא זוכר אם הם ביקשו לפתור את זה רקורסיבית, אבל בכל אופן הנה הדרך הרקורסיבית:

public static int gcd2(int a, int b) {
if (a == b)
return a;

if (a > b)
return gcd2(a - b, b);

return gcd2(a, b - a);
}אתה גם לא חייב לולאות while, for, foreach או do while. מספיק סוג אחד של לולאות. אבל בכל אופן, המציאו כמה סוגים לשם נוחות.

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


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

matan1212
28-08-2010, 22:57
ברק,התכוונת אולי למצוא את המכנה המשותף הקטן ביותר?

The_Ben
28-08-2010, 23:14
שאלה semi-קשורה: מה זה דרך רקורסיבית בתכנות? מה הכוונה בכתיבת תוכנה בדרך שכזו כלומר, ראיתי שהמונח נכתב מספר פעמים בפורום בהקשר של תכנות אבל לא הבנתי מאף אחד מהם מה זה למעשה אומר.

matan1212
28-08-2010, 23:18
שאלה semi-קשורה: מה זה דרך רקורסיבית בתכנות? מה הכוונה בכתיבת תוכנה בדרך שכזו כלומר, ראיתי שהמונח נכתב מספר פעמים בפורום בהקשר של תכנות אבל לא הבנתי מאף אחד מהם מה זה למעשה אומר.


לפי מה שהבנתי..אני אנסה להסביר בדרך פשוטה

יש פעולה שהיא abc, יש הוראה ללכת שמאלה שזה l,וימינה r

עכשיו

abc
{
r
l
abc
}

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

Dmot
28-08-2010, 23:23
אני הבנתי את זה כמו לולאה...
המתודה בעצם קוראת לעצמה שוב ושוב, עד שמגיעים לפעולה אליה מכוונת המתודה.
אז, אני יכול להגיד שיש דבר כזה רקורסיה אינסופית, כמו לולאה אינסופית, נכון?

matan1212
28-08-2010, 23:24
אני הבנתי את זה כמו לולאה...
המתודה בעצם קוראת לעצמה שוב ושוב, עד שמגיעים לפעולה אליה מכוונת המתודה.
אז, אני יכול להגיד שיש דבר כזה רקורסיה אינסופית, כמו לולאה אינסופית, נכון?


ברור....

The_Ben
28-08-2010, 23:25
לפי מה שהבנתי..אני אנסה להסביר בדרך פשוטה

יש פעולה שהיא abc, יש הוראה ללכת שמאלה שזה l,וימינה r

עכשיו

abc
{
r
l
abc
}

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

public static int gcd2(int a, int b) {
if (a == b)
return a;

if (a > b)
return gcd2(a - b, b);

return gcd2(a, b - a);
}

Dmot
28-08-2010, 23:26
אוקיי, ואיך זה בא לידי ביטוי למשל בקוד שפורסם כאן מקודם?:

public static int gcd2(int a, int b) {
if (a == b)
return a;

if (a > b)
return gcd2(a - b, b);

return gcd2(a, b - a);
}

המתודה קוראת שוב לעצמה בסוף, אבל עם מספרים אחרים.
זה מסתדר לי בראש (=
ברק, אני צודק? המורה אמרה לנו שרקורסיה זה חומר של יא, תמיד רציתי להבין (=

The_Ben
28-08-2010, 23:28
המתודה קוראת שוב לעצמה בסוף, אבל עם מספרים אחרים.
זה מסתדר לי בראש (=
ברק, אני צודק? המורה אמרה לנו שרקורסיה זה חומר של יא, תמיד רציתי להבין (=
לא שמתי לב שהיא מחזירה את עצמה בסוף באמת. תודה :) (ותודה למתן על ההסבר הראשוני).

Dmot
28-08-2010, 23:29
לא שמתי לב שהיא מחזירה את עצמה בסוף באמת. תודה :) (ותודה למתן על ההסבר הראשוני).
אני מנסה להבין בדיוק כמוך (=

The_Ben
28-08-2010, 23:30
אני מנסה להבין בדיוק כמוך (=
נשמע הגיוני מה שאמרת, נחכה אבל לאישור של מתן. נראה שהוא יודע את זה בוודאות (או הבין את זה...אחד מהשניים).

Netanelm7
28-08-2010, 23:38
כן כן רקורסיה זה פעולה ש"קוראת" לעצמה עד אשר מתקיים תנאי מסויים...

matan1212
28-08-2010, 23:41
המתודה קוראת שוב לעצמה בסוף, אבל עם מספרים אחרים.
זה מסתדר לי בראש (=
ברק, אני צודק? המורה אמרה לנו שרקורסיה זה חומר של יא, תמיד רציתי להבין (=


חח אצלנו רקורסיה זה חומר של י"ב...


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

ההסבר שהוא הביא נכון..

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

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

Netanelm7
28-08-2010, 23:45
חח אצלנו רקורסיה זה חומר של י"ב...

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

מסכים... צריך חשיבה מתמטית טהורה חחח.

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

לילה טוב לכם! :wink:

Dmot
28-08-2010, 23:45
חח אצלנו רקורסיה זה חומר של י"ב...



ההסבר שהוא הביא נכון..

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

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

Hurricane
28-08-2010, 23:47
אני לא מאמין..רק עכשיו הבנתי מה זה הדרך הרקורסיבית שתמיד מבקשים ולמה זה כזה קצר...זה כמו המשחק שפירסמת פעם..אבל מה יותר טוב דרך רקורסיבית או לולאה רגילה..? כאילו אני לא רואה הרבה הבדל..ודרך אגב הפיתרון שהצגתי הוא לא יותר פשוט ממערך..?
בעקרון מסתכלים קודם כל על סיבוכיות זמן ריצה שאת זה תלמדו על קצה המזלג בכיתה יא' (תרחיבו על זה באוניברסיטה\מכללה).
אחר כך מסתכלים על סיבוכיות המקום, כאשר במקרה הזה לולאה תמיד תהיה יעילה יותר שכן מחסנית זמן הריצה ברקורסיה מתמלאת בקצב מסחרר.

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


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

במספרים אחרים, 14 ו- 20, המכנה המשותף הגדול ביותר הוא 2.


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

דוגמא לפונקציה מתמטית תהיה סדרת פיבונאצ'י שבה מתקיים:
F_n=F_{n-1}+F_{n-2}
כאשר מתקיים:
F_1=0 \\ F_2=1


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

public static int sumOfDigits(int num) {
if (num < 10)
return num;
return num % 10 + sumOfDigits(num / 10);
}

בעצם בוא נבין את ההגיון.
נניח שיש לנו את המספר 12345, ונרצה למצוא את סכום ספרותיו.
אפשר לומר שבעצם סכום ספרותיו שווה בעצם לספרה האחרונה (חמש) ועוד סכום הספרות של המספר 1234.
אבל כאן לא עוצרים, אלא ממשיכים. סכום הספרות של המספר 1234 הוא הסכום של הספרה 4 ועוד סכום הספרות של המספר 123.
נמשיך כך עד שנגיע ל- 1.
קיבלנו מספר חד ספרתי. במקרה הזה, סכום הספרות הוא המספר עצמו, ולכן נפסיק.

עכשיו אם נסכום את מה שקיבלנו, נקבל 5+4+3+2+1 (מהסוף להתחלה).

matan1212
28-08-2010, 23:55
המכנה המשותף הקטן (וחיובי כמובן) של כל שני מספרים הוא 1.
לדוגמא, עבור המספרים 5 ו- 3, המספר 1 מהווה את המחלק הקטן ביותר.
בעוד שבמקרה הזה 1 גם מהווה את המחלק הגדול ביותר.

במספרים אחרים, 14 ו- 20, המכנה המשותף הגדול ביותר הוא 2).


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

The_Ben
28-08-2010, 23:59
תודה לכל מי שעזר לעיל, הבנתי מצויין עכשיו מה הכוונה בזה :).
אגב, את מדעי המחשב א' סיימתי (עושים את זה אצלנו בי"א) ואת השאר (מדעי המחשב ב' ועוד קורס אחד אם אני זוכר נכון, בשביל 5 יח"ל במדעי המחשב) אנחנו עושים השנה (י"ב). האם לומדים את נושא הרקורסיה בתכנות בחלק זה של 5 יחידות הלימוד? שכן בי"א לא למדנו את זה בכלל.

odp
29-08-2010, 00:01
רקורסיה זה בדיוק אינדוקציה. אם אתם יודעים אינדוקציה יהיה לכם יותר קל להבין מה זה רקורסיה.

נציג שתי שיטות לחישוב עצרת:

הדרך הרגילה (שכולנו הורגלנו בה לפני שלמדנו רקורסיה) :

עצרת(n)
1. solution=1
2. מ i=1 עד i<=n בצע
1.2 solution*=i
3. החזר solution

הדרך הרקורסיבית :

עצרת(n)
1. אם n=1
החזר 1
2. אחרת בצע
1.2 החזר n*עצרת(n-1)


עכשיו, מה הקשר לאינדוקציה? - אתם בוודאי שואלים. נעשה השוואה קצרה:

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

2. שלב ההנחה - נניח שהפונקציה עובדת ומחזירה את העצרת של מספר n-1 טבעי כלשהוא.

3. שלב ההוכחה - ידוע כי n!=(n-1)!*n (שלב 1.2 בפונקציה) , וכך הוכחנו את הפונקציה עבור n.


לרקורסיה, לפי דעתי, אין הרבה יתרונות - היא סותרת את עקרון ה- (KISS (Keep It Simple and Short, יותר קשה לעקוב אחריה ועוד. מה שכן, המיון המהיר משתמש בה ובעזרתה רץ מהר יותר משאר סוגי המיונים.

matan1212
29-08-2010, 00:18
רקורסיה זה בדיוק אינדוקציה. אם אתם יודעים אינדוקציה יהיה לכם יותר קל להבין מה זה רקורסיה.

נציג שתי שיטות לחישוב עצרת:

הדרך הרגילה (שכולנו הורגלנו בה לפני שלמדנו רקורסיה) :

עצרת(n)
1. Solution=1
2. מ i=1 עד i<=n בצע
1.2 solution*=i
3. החזר solution

הדרך הרקורסיבית :

עצרת(n)
1. אם n=1
החזר 1
2. אחרת בצע
1.2 החזר n*עצרת(n-1)


עכשיו, מה הקשר לאינדוקציה? - אתם בוודאי שואלים. נעשה השוואה קצרה:

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

2. שלב ההנחה - נניח שהפונקציה עובדת ומחזירה את העצרת של מספר n-1 טבעי כלשהוא.

3. שלב ההוכחה - ידוע כי n!=(n-1)!*n (שלב 1.2 בפונקציה) , וכך הוכחנו את הפונקציה עבור n.


לרקורסיה, לפי דעתי, אין הרבה יתרונות - היא סותרת את עקרון ה- (kiss (keep it simple and short, יותר קשה לעקוב אחריה ועוד. מה שכן, המיון המהיר משתמש בה ובעזרתה רץ מהר יותר משאר סוגי המיונים.

יש מצבים (אפילו רבים הייתי אומר) שאינדוקציה זה הדרך הכי נוחה לבדוק משוואות..

Hurricane
29-08-2010, 00:19
התכוונת אולי למחלק המשותף..ולא למכנה המשותף..מכנה משותף זה המספר שמתחלק ב-2 המספרים...בגלל זה לא יכול להיות הכי גדול..דרך אגב בשביל זה יש פיתרון ממש יותר פשוט (מבחינת היגיון) אבל הלולאה רצה יותר...רוצה אני אכתוב אותו?
לא יודע... באנגלית קוראים לזה Greatest common divisor.

בן, אני עשיתי את מדעי המחשב ב' בכיתה יא'. :P
נתנאל, דווקא אצלי זה ההפך. רקורסיה ממש קלה לי אבל עם מבני נתונים קשה לי (ועוד ביום רביעי יש לנו 3 שעות מבני נתונים O_O).

הממ... odp, אתה מתכוון ל- Merge sort?
ולא הבנתי מה הקשר לאינדוקציה... S:
רקורסיה זו לא הוכחה למשהו...

odp
29-08-2010, 00:20
מתן,

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

ברק,

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

Hurricane
29-08-2010, 00:23
נכון, אינדוקציה זה כלי מתמטי חשוב... איך זה קשור אבל לאינדוקציה? ם_o

matan1212
29-08-2010, 00:25
נכון, אינדוקציה זה כלי מתמטי חשוב... איך זה קשור אבל לאינדוקציה? ם_o


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

odp
29-08-2010, 00:27
נכון, אינדוקציה זה כלי מתמטי חשוב... איך זה קשור אבל לאינדוקציה? ם_o

איך לימדו אתכם רקורסיה בלי לקשר את זה לאינדוקציה? :blink:

Hurricane
29-08-2010, 00:28
באינדוקציה אתה מוכיח דברים ורקורסיה זאת הגדרה (כמו: "נוסחה מוגדרת ע"י כלל הנסיגה כך - בלה בלה בלה").

עכשיו כשקראתי שוב, הבנתי בערך לאן הוא חתר, אבל אותי אישית זה בלבל. ם_ם

odp
29-08-2010, 00:30
מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית - ויקיספר (http://he.wikibooks.org/wiki/%D7%9E%D7%91%D7%A0%D7%99_%D7%A0%D7%AA%D7%95%D7%A0% D7%99%D7%9D_%D7%95%D7%90%D7%9C%D7%92%D7%95%D7%A8%D 7%99%D7%AA%D7%9E%D7%99%D7%9D_-_%D7%9E%D7%97%D7%91%D7%A8%D7%AA_%D7%A7%D7%95%D7%A8 %D7%A1/%D7%A0%D7%A1%D7%A4%D7%97%D7%99%D7%9D/%D7%97%D7%A9%D7%99%D7%91%D7%94_%D7%A8%D7%A7%D7%95% D7%A8%D7%A1%D7%99%D7%91%D7%99%D7%AA)

הגדרה רקורסיבית – ויקיפדיה (http://he.wikipedia.org/wiki/%D7%94%D7%92%D7%93%D7%A8%D7%94_%D7%A8%D7%A7%D7%95% D7%A8%D7%A1%D7%99%D7%91%D7%99%D7%AA)

The_Ben
29-08-2010, 00:34
בן, אני עשיתי את מדעי המחשב ב' בכיתה יא'. :P

השאלה הייתה האם לומדים את זה במדעי המחשב ב', כלומר האם למדת את זה בי"א (שכן בשנה זו עשית את מדעי המחשב ב' :biggrin:).

Hurricane
29-08-2010, 00:34
^
הם מוכיחים באמצעות אינדוקציה שהפונקציה נכונה.
שים לב:
במתמטיקה (http://he.wikipedia.org/wiki/%D7%9E%D7%AA%D7%9E%D7%98%D7%99%D7%A7%D7%94) הגדרה רקורסיבית של מושג מתקבלת כהגדרה תקפה, אם אפשר להוכיח שהיא מספקת תשובה חד-משמעית בכל מקרה; ההוכחה היא בדרך כלל באינדוקציה (http://he.wikipedia.org/wiki/%D7%90%D7%99%D7%A0%D7%93%D7%95%D7%A7%D7%A6%D7%99%D 7%94_%D7%9E%D7%AA%D7%9E%D7%98%D7%99%D7%AA) או באינדוקציה טרנספיניטית (http://he.wikipedia.org/wiki/%D7%90%D7%99%D7%A0%D7%93%D7%95%D7%A7%D7%A6%D7%99%D 7%94_%D7%98%D7%A8%D7%A0%D7%A1%D7%A4%D7%99%D7%A0%D7 %99%D7%98%D7%99%D7%AA). הגדרה כזו נקראת הגדרה אינדוקטיבית

הם בעצם אומרים שההוכחה מתבצעת באמצעות אינדוקציה.

עריכה:
עשיתי את מדעי המחשב ב' בכיתה יא', ושם למדתי רקורסיה.

odp
29-08-2010, 00:39
השאלה הייתה האם לומדים את זה במדעי המחשב ב', כלומר האם למדת את זה בי"א (שכן בשנה זו עשית את מדעי המחשב ב' :biggrin:).

כן, רקורסיה זה חלק ממדעי המחשב ב' יחד עם מבני נתונים (מחסנית, רשימה, תור ועץ) ועם תכנות מונחה עצמים.



ברק,

אין וויכוח.

matan1212
29-08-2010, 06:05
אתה לא חייב לפתור את התרגיל בדרך רקורסיבית...
בעצם הפתרון מסתמך על זה שמתקיים:
gcd(a,b)=gcd(a-b,b)=gcd(a,b-a)

או פתרון טריוויאלי בג'אווה:

public static int gcd(int a, int b) {
while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}

return a;
}אני לא זוכר אם הם ביקשו לפתור את זה רקורסיבית, אבל בכל אופן הנה הדרך הרקורסיבית:

public static int gcd2(int a, int b) {
if (a == b)
return a;

if (a > b)
return gcd2(a - b, b);

return gcd2(a, b - a);
}אתה גם לא חייב לולאות while, for, foreach או do while. מספיק סוג אחד של לולאות. אבל בכל אופן, המציאו כמה סוגים לשם נוחות.

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


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

בקשר לשאלה עם התארכים איך עוזר לי המערך.?

matan1212
30-08-2010, 00:27
ברק,אתה יכול לענות על שאלתי (מה ששאלתי בתגובה ללמעלה) בבקשה..

Hurricane
30-08-2010, 11:10
אמרנו שמתקיים: gcd(a,b)=gcd(a-b,b) נכון?
עכשיו, בוא נסמן a-b=x ונקבל: gcd(a,b)=gcd(x,b) אבל אמרנו שמתקיים: gcd(a,b)=gcd(a-b,b) או במקרה הזה, אם נחליף את a ב- x נקבל:
gcd(x,b)=gcd(x-b,b).
או בעצם, אם נחזיר את ה- x ל- a-b נקבל:
gcd(a,b)=gcd(a-b,b)=gcd(a-2b,b)=...=gcd(a-mb,b)
כאשר הביטוי השמאלי גדול מהימני, נתחיל להקטין את הביטוי הימני. כלומר:
gcd(a,b)=gcd(a-mb,b-na)

או ניקח לדוגמא את שני המספרים 345 ו- 293, ונמצא את המחלק הגדול ביותר.
gcd(345,293)=gcd(345-293,293)= \\ gcd(52,293)=gcd(52,293-52)= \\ gcd(52,241)= \\ gcd(52,189)= \\ gcd(52,137)= \\ gcd(52,85)= \\ gcd(52,33) = \\ gcd(19,33)= \\ gcd(19,14)= \\ gcd(5,14)= \\ gcd(5,11)= \\ gcd(5,6)= \\ gcd(5,1)= \\ gcd(4,1)= \\ gcd(3,1) =\\ gcd(2,1)= \\ gcd(1,1) = 1

סמאל
30-08-2010, 13:19
רגע כל התרגילים האלה שאתם עושים פה .. איך בדיוק הם קשורים לדיון הזה d: ?

Hurricane
30-08-2010, 13:53
דיברנו על תרגילים ששואלים עליהם במבחני הקבלה לגאמ"א.

אילן
17-09-2010, 13:48
פיתרון של לוח השנה (אצלי זה למשל 2010)

public int dayInWeek(int day, int month)
{
int dayOn1.1 = 6;
int[] sumOfDays = new int[] {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}; //Amount of days past from 1.1 to 1.x
return (day-1 + sumOfDays[month-1]+dayOn1.1)%7;
}למשל אנחנו רוצים לדעת מה היום ב 27.5.2010
אז לוקחים מהמערך את הסכום של ארבעת החודשים שזה 120. (האלמנט הרביעי בהנחה שמתחילים מאפס).
מחברים 26 ימים כי 27.5 פחות 1.5 זה 26.5 אז בעצם מה 1.5 עד ל 27.5 עוברים 26 ימים.
ואז מחברים את היום שבו התחיל החודש(1.1)ואז עושים מודולו של 7.

matan1212
17-09-2010, 13:56
פיתרון של לוח השנה (אצלי זה למשל 2010)

public int dayinweek(int day, int month)
{
int dayon1.1 = 6;
int[] sumofdays = new int[] {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}; //amount of days past from 1.1 to 1.x
return (day-1 + sumofdays[month-1]+dayon1.1)%7;
}למשל אנחנו רוצים לדעת מה היום ב 27.5.2010
אז לוקחים מהמערך את הסכום של ארבעת החודשים שזה 120. (האלמנט הרביעי בהנחה שמתחילים מאפס).
מחברים 26 ימים כי 27.5 פחות 21.5 זה 26.5 אז מחברים 26 ימים בעצם.
ואז מחברים את היום שבו התחיל החודש(1.1)ואז עושים מודולו של 7.

איך 27.5 פחות 21.5 ייצא לך 26.5 הרי 27-21 שווה ל-6...ופה אתה צריך לדעת כל חודש כמה ימים..ויש שיטה איך אתה תוכל לעשות משהו שיעבוד בכל שנה...וגם לא הבנתי למה אתה עושה את זה כזה מסובך..הבאתי פיתאום שתוך שניות זה מביא....

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

אילן
17-09-2010, 13:57
איך 27.5 פחות 21.5 ייצא לך 26.5 הרי 27-21 שווה ל-6...ופה אתה צריך לדעת כל חודש כמה ימים..ויש שיטה איך אתה תוכל לעשות משהו שיעבוד בכל שנה...וגם לא הבנתי למה אתה עושה את זה כזה מסובך..הבאתי פיתאום שתוך שניות זה מביא....

דרך אגב באמת שלא הבנתי כלום ממה שעשית..אפשר הסבר יותר מפורט.?
טעות שלי,
27.5 פחות 1.5 יוצא 26.. הרי מיום ראשון עד ה27.5 עוברים 26 ימים..

matan1212
17-09-2010, 14:02
טעות שלי,
27.5 פחות 1.5 יוצא 26.. הרי מיום ראשון עד ה27.5 עוברים 26 ימים..

אז עשית כמו השיטה שלי..

אילן
17-09-2010, 14:05
איך 27.5 פחות 21.5 ייצא לך 26.5 הרי 27-21 שווה ל-6...ופה אתה צריך לדעת כל חודש כמה ימים..ויש שיטה איך אתה תוכל לעשות משהו שיעבוד בכל שנה...וגם לא הבנתי למה אתה עושה את זה כזה מסובך..הבאתי פיתאום שתוך שניות זה מביא....

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

1. אתה בודק מה הוא היום הראשון של השנה שזה ה1.1 (בינואר).
יום ראשון = 1, יום שני = 2, וכך הלאה עד יום שבת = 7.
ב1.1 ביונאר זה יום שישי, לכן שישי = 6.

2. אתה בודק מהו סכום הימים עד החודש שאתה רוצה למצוא, למשל אני רוצה למצוא יום מסויים במאי. אז אתה מחבר את ארבעת החודשים הקודמים ויוצא לך 120 (כמו באלמנט הרביעי במערך).

3. אתה מחבר את סכום החודשים שזה 120 עם מספר הימים מהראשון במאי עד ל 27 במאי כי אני רוצה למצוא את התאריך 27.5, ומספר הימים מה1.5 עד ל 27.5 זה כמו 27-1 שזה יוצא 26 ימים.

4. אתה מחבר את 120 עם 26 וגם מחבר את היום של ה1.1 בינואר שזה 6. יוצא לך :
120 + 26 + 6 = 152
עכשיו אתה עושה מודולו של 152 כך:
152%7 שזה 152 לחלק ל7 ואז אתה לוקח את השארית, השארית שקיבלת זה היום בעצם.
השארית היא 5, שזה יום חמישי.

אילן
17-09-2010, 14:06
אז עשית כמו השיטה שלי..
לא ראיתי את השיטה שלך, אבל זאת השיטה שלי :]

אילן
17-09-2010, 15:07
משולש פסקל
פיתרון השאלה :

static public ulong pascal(int place)
{
int row = ((int)Math.Sqrt((double)(1 + (place) << 3)) / 2) - 1;
int col = place - (((row + 1) * (row + 2)) >> 1) - 1;
col = Math.Min(col, row - col);
if (col == 0) return 1;
if (col == 1) return (ulong)row;
int dif = row - col;
bool[] c = new bool[col - 1]; //Initialize with false
ulong res = 1;
for (int i = dif + 1; i <= row; i++)
{
res *= (ulong)i;
for (int j = 0; j < (col - 1); j++)
if (!c[j] && res % (ulong)j == 0)
{
res /= (ulong)(j + 2);
c[j] = true;
}
}
return res;
}

matan1212
17-09-2010, 15:47
הסבר מורחב:

1. אתה בודק מה הוא היום הראשון של השנה שזה ה1.1 (בינואר).
יום ראשון = 1, יום שני = 2, וכך הלאה עד יום שבת = 7.
ב1.1 ביונאר זה יום שישי, לכן שישי = 6.

2. אתה בודק מהו סכום הימים עד החודש שאתה רוצה למצוא, למשל אני רוצה למצוא יום מסויים במאי. אז אתה מחבר את ארבעת החודשים הקודמים ויוצא לך 120 (כמו באלמנט הרביעי במערך).

3. אתה מחבר את סכום החודשים שזה 120 עם מספר הימים מהראשון במאי עד ל 27 במאי כי אני רוצה למצוא את התאריך 27.5, ומספר הימים מה1.5 עד ל 27.5 זה כמו 27-1 שזה יוצא 26 ימים.

4. אתה מחבר את 120 עם 26 וגם מחבר את היום של ה1.1 בינואר שזה 6. יוצא לך :
120 + 26 + 6 = 152
עכשיו אתה עושה מודולו של 152 כך:
152%7 שזה 152 לחלק ל7 ואז אתה לוקח את השארית, השארית שקיבלת זה היום בעצם.
השארית היא 5, שזה יום חמישי.


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

נגיד 27 במאי ומאי מתחיל ביום שבת..כולומר 0 או 7..עכשיו 27-1=26 ואז 26+0=26 מודולו 4 ייצא לך 5 כלומר יום חמישי
אמרת אתה לא יודע תכנות...מה קרה?

אילן
17-09-2010, 15:49
שיטה קצת ארוכה...וקצת לא טובה...אתה מכניס במערך את כל הימים שבהם החודש מתחיל...בקיצר סתכל כמה תגובות ותראה....

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

matan1212
17-09-2010, 15:59
משולש פסקל
פיתרון השאלה :

static public ulong pascal(int place)
{
int row = ((int)math.sqrt((double)(1 + (place) << 3)) / 2) - 1;
int col = place - (((row + 1) * (row + 2)) >> 1) - 1;
col = math.min(col, row - col);
if (col == 0) return 1;
if (col == 1) return (ulong)row;
int dif = row - col;
bool[] c = new bool[col - 1]; //initialize with false
ulong res = 1;
for (int i = dif + 1; i <= row; i++)
{
res *= (ulong)i;
for (int j = 0; j < (col - 1); j++)
if (!c[j] && res % (ulong)j == 0)
{
res /= (ulong)(j + 2);
c[j] = true;
}
}
return res;
}

באיזה שפה כתבת את זה.?זה נראה כמו c# אבל יש פי כמה סימנים שאין ב-c# כמו << ...ואפשר הסבר מה עשית פה?

אילן
17-09-2010, 16:20
באיזה שפה כתבת את זה.?זה נראה כמו c# אבל יש פי כמה סימנים שאין ב-c# כמו << ...ואפשר הסבר מה עשית פה?
זה לא אני כתבתי.. זה חבר שלי כתב.. אני בעצמי לא הבנתי

Hurricane
17-09-2010, 17:24
ב- C# יש >>... אלו פעולות על סיביות (Bits). אתה לא תלמד את זה בבצפר.

anitov
18-09-2010, 10:56
משולש פסקל הכי נחמד ויפה רקורסיה.
מישהו לא מזמן היה שאלה עם תור...

אילן
18-09-2010, 12:04
מהי השאלה?

anitov
18-09-2010, 21:43
בפרטי :)

igngaea
09-12-2012, 07:49
הנה התשובה חברים :)



static void Main(string[] args)
{
Console.Write("Index in pascal triangle: ");
int i = int.Parse(Console.ReadLine());
Console.WriteLine("Value in pascal triangle by index: " + ValueInPascalTriangleByIndex(i));
}
static int ValueInPascalTriangleByIndex(int i)
{
int pos = 1;
int r = 0;
int c = 0;
while (pos != i)
{
if (r == c)
{
r++;
c = 0;
}
else
{
c++;
}
pos++;
}
return (Factorial(r) / (Factorial(c) * Factorial(r - c)));
}
static int Factorial(int n)
{
if (n == 0)
{
return 1;
}
return n * Factorial(n - 1);
}


זה הכל :) מקווה שעזרתי במשהו...