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

קוד:

10 54 
2 43
7 54
90 8
2 62

התוצאה תהייה :

קוד:

10 54	-> (2,43) (2,62) (7,54)
2 42	-> (2,43) (2,63) (7,54)
7 54	-> (10,54) (2,62) (2,43)
90 8 	-> (10,54) (7,54) (2,62)
2 62	-> (2,54) (2,43) (7,54)

בהתחלה חשבתי שאני אמור לייצג את הנתונים ע"י גרף, או עץ מסויים - אבל זה לא ניראה לי הגיוני אחרי זמן מסויים, הרי אם
הקובץ עצמו היה בגודל של 50mb, מה הסיכוי שהתכנית הייתה רצה בפחות מ n^2 ? אז הבנתי שבעצם אני צריך מן חיפוש מסויים
הבעיה היא שאין לי ממש כיוון כלשהו לחיפוש הזה, או בכלל רעיון להתחלה כלשהי,
מישהו יכול לתת לי כיוון כלשהו ?

תודה מראש (:

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

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

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

קוד:

45 67
12 99
23423 45
3 44
24 78
23 8
56 67
09 5698

והלך והלך.

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

קוד:

45 67 -> (56 67) (24 78) (23 8)

וככה להמשיך לכל שאר הזוגות;

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

תודה (;

איך אתה מגדיר קירבה?

זה יכול להיות המרחק של כפולות של זוגות, או המרחק של סכומי זוגות, או המרחק של הפרש זוגות..

!!אזהרה!!

ההודעה עלולה להכיל שברי אגוזים ו/או איברי דגים כלשהם

!!אזהרה!!

בפשטות למדי, כמו שאתה סופר רגיל, לדוגמא,
יש לנו את הסידרה

קוד:

2 5 
21 54 
17 15 
18 17
92 89

הזוג הראשון (2,5) הכי קרוב ל 15,17
הזוג השני (54,21) הכי קרוב ל89,92
הזוג השלישי (15,17) הכי קרוב ל18,17
הזוג הרביעי(89,92) הכי קרוב ל54,21
והלך והלך, אין פה שום טריק או משהו מסובך מזה.

אתה חייב להגדיר כיצד זוג מספרים "קרוב" לזוג מספרים אחר...

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

וכו'...

אתה חייב להגדיר משהו ברור..

ציטוט:

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

לזה התכוונתי (:

אני מניח שלכל הנ"ל התכוונת כולל המשפט (שמשום מה החסרת):

ציטוט:

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

שאלה נוספת:
האם הבדיקה היא בהתאמה לפי האינדקס של המספר כפי שהוא כתוב,
או בדיקה בהתאמה לפי המספר הנמוך\הגבוה ביותר מבין השניים?

כלומר, יש לי את המספרים הבאים:

קוד:

58 90
60 25

אז להשוות באופן הבא:
58 מול 60, ו-90 מול 25.

או להשוות באופן הבא:
58 מול 25, ו- 90 מול 60.

???

58 מול 60 ו90 מול 25

אוקי...

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

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

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

קוד:

#define L	20	// Number of integer pairs (or, Lines...) to receive
#define r	3	// r = return ; How much pairs to return?
#define r_P	((r % 2)? 1 : 0 )	// r is pair?
#define r_H (r/2)	// Divide r by 2

int main(void)
{
	int num1[L], num2[L],	 // Contains the data/numbers 
		idx1[L], idx2[L],	// Pointers to data new index
		pairs[L][r+1][2];		// The result/final array. The first member in pairs[L] has the data of the pair numbers. The rest members are the closest pair numbers.
	
	for(int i=0; i<L; ++i)
		scanf("%d %d", &num1[i], &num2[i]);
	
	int tmp = 0;	// Save temporary number

	// sort num1[]
	for(int i=L-1; --i; )
		for(int x=i-1; --x; )
			if (num1[i]<num1[x]) {
				// Switch places
				tmp=num1[i];
				num1[i]=num1[x];
				num1[x]=tmp;
				
				// Save index
				idx1[i]=x;
				idx1[x]=i;
			}
	
	// sort num2[]
	for(int i=L-1; --i; )
		for(int x=i-1; --x; )
			if (num2[i]<num2[x]) {
				// Switch places
				tmp=num2[i];
				num2[i]=num2[x];
				num2[x]=tmp;
				
				// Save index
				idx2[i]=x;
				idx2[x]=i;
			}
	
	
	// Now we have the sorted numbers, with their new/old index
	// So check the closest numbers, according to the new index of both numbers
	
	for(int i=L-1; --i; )
	{
		int idx_diff = idx1[i] - idx2[i];

		if (!idx_diff)	// New index for both numbers is equal
		{
			if (r_P) // r is pair?
				// Enter to the final array all the closest numbers
				for (c=r_H; --c; )
				{
					pairs[i][c] = {num1[ idx1[i]+c ], num2[ idx2[i]+c ]};
					pairs[i][c] = {num1[ idx1[i]-c ], num2[ idx2[i]-c ]};
				}
			else	// r is NOT pair.
			{
				// Enter to the final array all the closest numbers
				// AND validate the last pair of numbers... (who's greater?)
				for (c=1; c<r_H-1; ++c )
				{
					pairs[i][c] = {num1[ idx1[i]+c ], num2[ idx2[i]+c ]};
					pairs[i][c] = {num1[ idx1[i]-c ], num2[ idx2[i]-c ]};
				}
				
				
				if 	( 
						// (function abs() returns the absolute value of an integer)

						abs( num1[ idx1[i]+r_H ] - num1[ idx1[i] ] ) + abs( num2[ idx2[i]+r_H ] - num2[ idx2[i] ] )
						<
						abs( num1[ idx1[i]-r_H ] - num1[ idx1[i] ] ) + abs( num2[ idx2[i]-r_H ] - num2[ idx2[i] ] )
					)
					pairs[i][r+1] = { num1[ idx1[i]+r_H ], num2[ idx2[i]+r_H ] ] };
				else
					pairs[i][r+1] = { num1[ idx1[i]-r_H ], num2[ idx2[i]-r_H ] ] };
			}
		}
		
		// In the following cases, check the numbers in the middle location in the array...
		// If the difference of locations is fewer than r, enter all the members in the middle
		//	and return back to the algorithm displayed in the first condition (above)
		
		elseif (idx_diff > 0) // Index of num1 is greater than of num2
		{
			// EMPTY. Left for you.
		}
		else	// Index of num2 is greater than of num1
		{
			// EMPTY. Left for you.
		}
	}
	

	return 0;
}

אני לא חושב שגם עם "חיפוש" כלשהו על כל אחד מהערכים, לא תקבל יעילות טובה יותר מ n^2.

הרי אם לא תסדר אותם בסדר כלשהו, תצטרך עבור כל זוג (שורה) לעבור על כל שאר הזוגות, שזה N פעמים לעבור על N, שזה יעילותו של N^2 (אל תשכח, שאתה צריך לשמור 3 ערכים, אז עבור כל זוג, תצטרך גם לעבור על מערך של 3..)

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

!!אזהרה!!

ההודעה עלולה להכיל שברי אגוזים ו/או איברי דגים כלשהם

!!אזהרה!!