יש לי את השאלה :
כתבו פונקציה המקבלת מערך וגודלו, ומחזירה אמת אם יש 2 איברים שווים במערך.
ושהסיבוכיות תהיה (o(nlogn
את זה אני יודע לעשות, אבל בסיבוכיות של o(n^2) עם 2 לולאות

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

תחשוב על מיון מיזוג, ותוסיף לפונקציה מיזוג שברגע שהיא משווה בין האיברים של שני מערכים בגודל פחות מN בצורה לינארית, שאם a[i]==a[j] אז היא תשנה דגל. ככה, מספר הפעולות יהיה מקסימום An*log(n)
ואם יהיו שני איברים שווים, אז בשלב מסויים בטוח יהיו תתי מערכים שכל אחד מכיל לפחות איבר אחד מהשווים, וזה יעבור על כל אינדקס (פחות מ2n מעברים)...זה הכל.

אם תרצה אני אכתוב לך קוד...

Any sufficiently advanced bug is indistinguishable from a feature

הפונקציה שרצית - IsThere

מקבלת מערך וגודל, משתמשת בפונקציה func בשביל
לקרוא לעצמה ~logn פעמים בריקורסיה ובכל הרצה לעבור a*n מעברים על איברים מתת-המערך הנוכחי (שמוגדר ע"י low, high, mid).
בקיצור a*n*logn פעולות.
תחזיר 1 אם קיים איבר בarr שמופיע פעמיים או יותר, אחרת 0.

קוד:

#include <stdio.h>
 
#include <conio.h>
int flag;
 
 
int func(int arr[], int low, int high){
int mid,i,j,k;
if(low<high)
{
mid=(low+high)/2;
func(arr,low,mid);
func(arr,mid+1,high);
i=low;
j=mid+1;
k=i;
int c[500];
while((i<=mid)&&(j<=high))
{
if(arr[i]<arr[j])
{
c[k]=arr[i];
k++;
i++;
}
else if (arr[i]==arr[j]){
flag=1;
k++;
i++;
}else{
c[k]=arr[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=arr[i];
k++;
i++;
}
while(j<=high)
{
c[k]=arr[j];
k++;
j++;
}
for(i=low;i<k;i++)
{
arr[i]=c[i];
}
 
} return flag;
}
 
int IsThere(int arr[], int size){
flag = 0;
return func(arr,0,size-1);
}
 
 
int main(){
int arr[] = {411, 41, 11, 33,19, 3, 1,50, 111, 4};
printf("%d",IsThere(arr,10));
getch();
} 

Any sufficiently advanced bug is indistinguishable from a feature

תודה רבה :]


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

תשתמש במשתנים גלובליים כמשתני עזר בפונקציות ריקורסיביות...

Any sufficiently advanced bug is indistinguishable from a feature

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

קוד:

function first (num:integer; he:integer):integer;
begin
	if (he = trunc(num / he)) then
		begin
			first:=1;
			exit;
		end
		  else
			if ((num / he) = trunc(num / he)) then
				begin
					first:=0;
					exit;
				end
			else
				first:=first(num,he+1);
end

;

1.במקרה הזה אתה לא צריך לקבל את he, בגלל שאתה לא צריך לחזור לרמת קינון ריקורסיה קודמת כלשהי, אז אתה לא צריך את מנגנון הריקורסיה עבורו.
לכן, במקום לקבל אותו כארגיומנט של first, אתה יכול להגדיר אותו כמשתנה גלובלי, ואיפה שאתה קורא ל
First(num, he+1) פשוט לעשות
he:=he+1;
First(num);
עכשיו איפה מתעוררת הבעיה? בערך הראשוני ש he יקבל. שהרי אם תציב בו ערך בפונקציה, הוא יקבל את זה בכל פעם שהיא קוראת לעצמה.
אז יש לך 2 אפשרויות:
א.בבלוק הראשי, לקבוע ש he:=2;.
ב.להשתמש במשתנה בתור דגל/מונה ואז לכתוב בתוך first , בהתחלה, תנאי שרק אם flag=0 נניח אזי he:=2;.


2.שכחתי נקודה פסיק בend האחרון.

3.יכולת במקום לבדוק עם החלוקה שווה לעיגול למטה של החלוקה, לעשות if num mod he = 0 :/ (ואז איפה שאתה כותב if he = trunc(num/he) שזה, בשביל שהפונקציה תרוץ עד העיגול של שורש(num), להשתמש באותה צורה..)

Any sufficiently advanced bug is indistinguishable from a feature

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

פשוט תצהיר he:integer; בראש התכנית, לפני הפונקציה.
זה יהיה משתנה גלובלי, ותוכל לפנות ולשנות אותו מתוך הפונקציה...

Any sufficiently advanced bug is indistinguishable from a feature

(אני לא נוגע בפסקל בד"כ)
...זה עובד, ומצאתי טעות קטנה בתכנית שלך.
הנה התכנית ללא שימוש בארגיומנט נוסף מאשר num:

קוד:

 

var
he,n:integer;

function prime(num:integer):integer;
begin
n:=sqrt(num);
		if (he = trunc(n)) then
		begin
				prime:=1;
				exit;

		end
		else if (num mod he = 0 ) then
		begin

				prime:=0;
				exit;
		end
		else
		begin
				he:=he+1;
				prime:=prime(num);
		end;
end;

הטעות שלך היא, שקודם כל ברור שאם

x=y/x אז x=שורש(y)

,אבל אתה משתמש בזה לא נכון (זה יעבוד ברוב המקרים, אבל נסה לדוגמא לתת לפונקציה את הערך 47...סתם לדוגמא. הסבר למה זה לא עובד לדוגמא במקרה הזה להלן)
עכשיו he מקבל ערכים שלמים. נניח שhe מגיע לשלם הגדול ביותר שיותר קטן משורש(num), אז אתה מניח שעיגול_למטה(שורש(num)) = עיגול_למטה(num/he) , אבל זה לא נכון בכל המקרים כי he הוא לא מספר שעבורו he=num/he אלא רק שווה לעיגול של num/he. כלומר אם החלק הלא-שלם של שורש(num) גדול מ0.5, זה לא לא יקיים לעולם את התנאי הראשון, ויגיע בסופו של דבר לתנאי השני (כש he=num) ויחזיר 0 למרות שNum ראשוני. מקרה כזה לדוגמא, הוא Num=47.

Any sufficiently advanced bug is indistinguishable from a feature

ומה ההבדל בין לעשות מה שאתה עשית לבין לעשות כמו שעשיתי והאם זה אפשרי ועונה על דרישת השאלה?

קוד:

function prime (num:integer):integer;
begin
			   prime:=first(num,2);
end;

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

Any sufficiently advanced bug is indistinguishable from a feature

סבבה , תודה