פתרון רקורסיה מסויימת

[SweeT_EviL]

השאלה בתמונה..

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

מה אתם אומרים?

עריכה:

אה, זה בC/C++ אם למישהו משנה

[attachment deleted by admin]

[The_Doom_Master]

כן אתה צריך לחשוב על String כמערך של Chars

אז למשל אתה נמצא על האות 0

שזה char[0] האות הבא ב String היא char[1]

פשוט תיקח את ה String.Length כסיום הפונקציה

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

לעשות רקרוסיה פנימית שעוברת על String עד שמגיעה לאות שאתה בה עכשיו ומשווה את ה char[1] עם האות הבאה..

זה רק שיטה אחת יש עוד הרבה..

[שניצל]

אי אפשר לקחת את string.length כסיום הפונקציה, כי הוא ב-C ולא ב-C#. חוץ מזה, נאסר עליו ספציפית להשתמש ב-strlen.

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

הנה הפתרון שלי:

void myFund(char* str)
{
 tmpFunc(str+1, str[0]);
}


char tmpFunc(char* str, char firstChar)
{
 if str[1] == 0)
 {
  return str[0];
 }
 else
 {
  char lastChar = myFunc(str+1, firstChar);
  if (str[0] > firstChar && str[0] < lastChar)
  {
   printf("%c", str[0]);
  }  
 }
}

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

[Ghosthunter]

ולפי מה שאני הבנתי:

void func(char *str)
{
	if(str[0]=='\0' || str[1]=='\0')
		return;
	if(str[0]>128)//not first ite
	{
		if(str[0]-128+1 == str[1] || str[1]-128 == str[0]+1)
			printf("%c%c", str[0]-128, str[1]);
	}

	str[1] += 128;
	func(str+1);
	str[1] -= 128;
}

בהנחה שזו מחרוזת שבנוייה מאותיות, ולא מדברים אחרים לא קשורים.

[SweeT_EviL]

אי אפשר לקחת את string.length כסיום הפונקציה, כי הוא ב-C ולא ב-C#. חוץ מזה, נאסר עליו ספציפית להשתמש ב-strlen.

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

הנה הפתרון שלי:

void myFund(char* str)
{
 tmpFunc(str+1, str[0]);
}


char tmpFunc(char* str, char firstChar)
{
 if str[1] == 0)
 {
  return str[0];
 }
 else
 {
  char lastChar = myFunc(str+1, firstChar);
  if (str[0] > firstChar && str[0] < lastChar)
  {
   printf("%c", str[0]);
  }  
 }
}

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

ממה שאני מבין מהתוכנית הזו

השורה הזו

char lastChar = myFunc(str+1, firstChar);

אמורה להחזיר את הערך האחרון במחרוזת, אבל נראה לי שהיא תמיד תחזיר את הערך הראשון במחרוזת, לא?( ד"א אני מניח שפה התכוונת לtmpFunc(..) ולא לmyFunc(..) )

כי בסוף הוא תמיד יכנס לזה

if str[1] == 0)
 {
  return str[0];
 }

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

1.abcd

acbd.2

acdb.3

xabcde.4

זה מה שיודפס מכל אחת מהמחרוזות:

1. bc

2.c

3. כלום

4. כלום

ולפי מה שאני הבנתי:

void func(char *str)
{
	if(str[0]=='\0' || str[1]=='\0')
		return;
	if(str[0]>128)//not first ite
	{
		if(str[0]-128+1 == str[1] || str[1]-128 == str[0]+1)
			printf("%c%c", str[0]-128, str[1]);
	}

	str[1] += 128;
	func(str+1);
	str[1] -= 128;
}

בהנחה שזו מחרוזת שבנוייה מאותיות, ולא מדברים אחרים לא קשורים.

מה128 מייצג, a?

ומה זה עוזר שאתה שולח לו כל הזמן str+1 אם אתה מתייחס תמיד ל str[0] ו str[1]

לגבי שתיכם, אם אני טועה- תקנו אותי! רק אתמול חזרתי לC ועדין לא התעמקתי במחרוזות(lame excuse =/)

עריכה:

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

[Zelig]

הנה פתרון (שלא בדקתי אם הוא עובד או אפילו מתקמפל כי אני עצלן):

char func( char* str )
{
	char first_char, last_char;

	// pathological case of empty input or input with one character
	if ( str[0] == 0 ) return 0; 
	if ( str[1] == 0 ) return str[0];

	// recursive termination, or the pathological case of two character input
	if ( str[2] == 0 ) return str[1];

	first_char = str[0];

	swap_single_character( str, str+1 );
	last_char = func( str+1 );
	swap_single_character( str, str+1 );

	if ( ( first_char <= str[1] ) && ( str[1] <= last_char ) )
		putc( str[1] );

	return last_char;
}

מס' נקודות:

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

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

* כתוצאה מכך כל שלב ברקורסיה יודע (בדרך חזרה מהרקורסיה!) מי האות האחרונה ומי האות הראשונה.

* הציטוט ש-unsigned integer משתמש בו זה לא ממני, זה מויקיפדיה.

עריכה: זה לא מטפל במקרה שהמצביע הוא NULL.

[Ghosthunter]

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

2) str+1 מציין את הפוינטר לאות הבאה. זה כמו לרשום &a[1], רק זול יותר.

3) הראתי את הציטוט לחבר שלי והוא התלהב.

[Zelig]

כן, גם אצלי כולם התלהבו מהציטוט. הנה עוד כמה: http://en.wikiquote.org/wiki/Programming

[שניצל]

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

1.abcd

acbd.2

acdb.3

xabcde.4

זה מה שיודפס מכל אחת מהמחרוזות:

1. bc

2.c

3. כלום

4. כלום

אתה בטוח? כי לפי מה שאתה אומר, יש כמה הדפסות אפשריות לכל מחרוזת. בדוגמאות שנתת, ב-2 אפשר להדפיס או b או c.

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

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

לגבי ה-str+1, כמו שאמרו כאן, זה המחרוזת ללא התו הראשון. יש לי פתרון שקול שאולי יהיה יותר מובן (לפי איך שאני מבין את התרגיל):

void myFunc(char* str)
{
 tmpFunc(str, 1);
}


char tmpFunc(char* str, int pos)
{
 if (str[pos+1] == 0)
 {
  return str[pos];
 }
 else
 {
  char lastChar = tmpFunc(str, pos+1);
  if (str[pos] > str[0] && str[pos] < lastChar)
  {
   printf("%c", str[pos]);
  }  
 }
}

[B.D.B]

dunno if it'll help you, but here's a function I wrote for receiving a string without knowing it's length.

#include<mem.h>
#include<conio.h>

int getstring(char **string,int lenth);

int main()
{
char **str;
clrscr();
getstring(str,0);
puts(*str);
free(*str);
return 0;
}


int getstring(char **string,int lenth)
{
char ch;
if (lenth==0)
fflush(stdin);
ch=getchar();
if (ch==10)
{
*string=(char *)malloc((lenth+1)*sizeof(char));
*(*string+lenth)='\0';
return lenth-1;
}
else
*(*string+getstring(string,lenth+1))=ch;
if (lenth==0)
{
fflush(stdin);
return 0;
}
return lenth-1;
}

#include<stdio.h>

[Zelig]

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

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

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

בקריאה שניה של ההוראות, נראה לי שהיה מקום לומר במפורש אם מותר או אסור להעביר פרמטרים נוספים.

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

[שניצל]

הגרסה שלי לא מטפלת טוב בהרבה דברים, לא ממש טרחתי להוסיף בדיקת קלט (הנחתי שהמחרוזת לפחות בגודל 2, ומכילה רק אותיות אנגליות באותו case).

הממ עכשיו כשאני מסתכל שוב על השאלה, נתקלתי במשפט הבא:

"כתוב פונקציה רקורסיבית המקבלת מחרוזת..."

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

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

char myFunc(char* str)
{
 static int pos = 0;
 int currentpos = pos;

 if (str[pos+1] == 0)
 {
  // reset pos, because this is the last char
  pos = 0;
  return str[pos];
 }
 else
 {
  ++pos;
  char lastChar = tmpFunc(str);
  if (str[currentpos] > str[0] && str[currentpos] < lastChar)
  {
   printf("%c", str[currentpos]);
  }  
 }
}

(יש לציין שהפונקציה שלי אינה thread-safe, אבל זו לא ממש הייתה דרישה...)

[Zelig]

משתנים גלובלים הם השטן!!!11

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

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

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

[שניצל]

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

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

ברור שמשתנים גלוגליים/סטטיים הם השטן, זה היה סתם בשביל הכיף.

[Zelig]

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

טוב, זה מה שמגיע לי שכאני לא ממש קורא את התוכנה.

מישהו שאני מכיר השתמש בהרבה משתנים גלובליים, ושבוע אח"כ סבתא שלו נפלה במדרגות, התוכי שלו התעטש והאוטו שלו נשרף!