יש לי שאלה

נתון מערך A שבו N מספרים טבעיים, כמו כן נתון מספר טבעי a , רוצים לדעת האם קיימים שני מספרים m n המקיימים a=m/n סיבוכיות הפיתרון צריכה להיות ליניארית

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

קוד:

short ratio_exists(unsigned int* num, int size, unsigned int ratio)
{
	unsigned int i, x, tmp;

	for(i=0; i<size; ++i)
		if (!(tmp = *(num+i) % ratio))	// Is that equals zero?
		{
			for(x=0; x<size; ++x)
				if (tmp == *(num+x))
					return 1; // We fount the proper ratio
		}

	return 0;
}

int main(void)
{
	unsigned int num[10] = { 5, 3, 1, 88, 32, 90, 100, 31, 6, 14 },
		a = 2;
	
	if (ratio_exists(num, sizeof num, a))
		printf("Our ratio is: %d ! yay...", a);
	
	return 0;
}

זה לא עוזר לי מכיוון שזה צריך להיות בסיבוכיות ליניארית , מה שרשמת זה N בריבוע,

זה בכלל הגיוני?

בעיקרון יש פה צורך לחלק כל מספר במערך בכל מספר אחר.
מה שמרמז על סיבוכיות של [tex] \mathcal{O} \left( n^2 \right) [/tex]

אבל...
יש אלגוריתמים של מיון בהשוואה שעושים דברים כאלה בסיבוכיות של [tex] \mathcal{O} \left({n \log n} \right) [/tex]
ולאלה יש הוכחה שלא ניתן לרדת מתחת לסיבוכיות הזו:
http://en.wikipedia.org/wiki/Compar...o_ sort_a_list


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

_________________________________________________

אזהרה: משרד הבריאות קובע כי העישון מזיק לבריאות !
תראו, אפילו החייזר נהיה ירוק מזה

מנהל פורום מדע בדיוני ופנטסיה ופורום מדע טכנולוגיה וטבע בפרש

פתרון לינארי :

תעבור על המערך פעם אחת ותמצא את המקסימום - לינארי

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

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

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

מקווה שזה ברור .....
סה"כ יש לך פה יצירה של מערך חדש ומעבר של 3-4 פעמים על המערך המקורי ולכן לינארי

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

ואני ישאיר לכם לחשוב למה, אם תרצו הסבר תגידו....

ואם המספר הכי גדול במערך הוא 9223372036854775807?

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

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

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

(שים לב שהיו רק מס' דקות לענות על השאלה)

_________________________________________________

אזהרה: משרד הבריאות קובע כי העישון מזיק לבריאות !
תראו, אפילו החייזר נהיה ירוק מזה

מנהל פורום מדע בדיוני ופנטסיה ופורום מדע טכנולוגיה וטבע בפרש

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

אהה... ואת החידה אני מכיר

בגלל שהאלגוריתם הוא לינארי מבחינת זמן הריצה
לא ראיתי שם דרישה לליניאריות של כמות הזיכרון.

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

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

_________________________________________________

אזהרה: משרד הבריאות קובע כי העישון מזיק לבריאות !
תראו, אפילו החייזר נהיה ירוק מזה

מנהל פורום מדע בדיוני ופנטסיה ופורום מדע טכנולוגיה וטבע בפרש

מה התשובה לחידה...?

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

קוד PHP:

<?php

$lights = array();

for($i=1; $i<101; ++$i)    # ppl
    for($x=1; ($tmp = $x*$i)<101; ++$x)    # lights
        if ($tmp<101)
            $lights[$tmp] = $lights[$tmp] ? false : true;

foreach ($lights as $k=>$v)
    if (!$v)
    {    unset($lights[$k]);    }

echo '<code style="white-space:pre;">';
print_r($lights);
echo '</code>';

?>

הפיתרון ( כלומר הפלט של הקוד הנ"ל ):

קוד:

Array
(
    [1] => 1
    [4] => 1
    [9] => 1
    [16] => 1
    [25] => 1
    [36] => 1
    [49] => 1
    [64] => 1
    [81] => 1
    [100] => 1
)