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

יכול להיות ששכחת לציין שהמערכים ממויינים?

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

והערכים גם יכולים לחזור על עצמם.
למשל:

קוד:

int A[] = {23, 45, 56, 0, 4, -4, 55}
int B[] = {22, 55, 4, -5}

התת מערך יהיה:

קוד:

23,56,4,-4

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

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

סליחה, "...חייב להיות כמו במערך הקטן..."

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

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

קוד:

int crypt_subarr(int a[], int b[], int n, int m)
{

	if(n==0)
	{
		if(m==0)
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}

	if(a[n-n]==b[m-m] || a[n-n]==(b[m-m]-1))
	{
		return crypt_subarr(a+1, b+1, n-1, m-1);
	}
	else
	{
		return crypt_subarr(a+1, b, n-1, m);
	}

	return -1;
}

נסי את זה (מקווה שאין טעויות):

קוד:

		public static int crypt_subarr(int[] a, int[] b, int n, int m)
		{
			if (a[n - 1] == b[m - 1] || a[n - 1] == b[m - 1] + 1)
			{
				if (m == 1)
					return 1;
				return crypt_subarr(a, b, n - 1, m - 1);
			}
			else
			{
				if (n == 1)
					return 0;
				return crypt_subarr(a, b, n - 1, m);
			}
		}

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

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

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

a[n-n]==b[m-m] || a[n-n]==b[m-m]-1

- מה אומר n-n או m-m? זה יביא תמיד 0, אני מניח שהתכוונת לרשום n-1 ו-m-1.

- בחלק השני של התנאי, את צריכה לבדוק ש- a[n-n]==b[m-m]+1 מכיוון שיש להוסיף 1 לאיבר הקטן כדי שיתקיים שוויון (או להחסיר 1 מהאיבר הגדול).

return crypt_subarr(a+1, b+1, n-1, m-1);q
return crypt_subarr(a+1, b, n-1, m);q

- אני לא יודע איך זה בשפת C, אבל בכל שפות התכנות שאני מכיר שתי השורות הללו יביאו לשגיאת קומפילציה. אי אפשר לעשות פעולה חשבונית a+1 כאשר a הוא מערך... גם אין בזה ממש הגיון

עוד משהו, התנאי שלך בהתחלה עובד ללא תלות בכך ש-יש/אין התאמה, ז"א... את חייבת לבדוק:

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

(אפשר אפילו לשפר טיפה את הקוד ולהוסיף את התנאי "אם n<m אז החזר 0").

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

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

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

בברכה, מתן.
www.MatanNarkiss.com

הספיקו להעיר לי על זה לפנייך

בכל מקרה, אין הגיון לעשות את זה בדוגמת הקוד שהיא כתבה, שהרי היא מבצעת את כל הבדיקות עם n ו-m כאינדקסים של המערך...

ציטוט:

במקור נכתב על ידי Michael Shermer Smart people are very good at rationalizing things they came to believe for non-smart reasons.

טעות, למחוק

בברכה, מתן.
www.MatanNarkiss.com