ביינערי זוכן - איינער פון די יזיאַסט וועגן צו געפינען אַן עלעמענט אין אַ מענגע

גאַנץ אָפֿט, פּראָוגראַמערז, אַפֿילו ביגינערז, פאַסעד מיט די פאַקט אַז עס איז אַ סכום פון נומערן, וואָס מוזן געפֿינען אַ ספּעציפיש נומער. עס איז דעם זאַמלונג איז גערופֿן אַ מענגע. און צו געפינען זאכן אין עס, עס זענען אַ מיריאַד פון וועגן. אבער דער רובֿ פּשוט פון זיי קענען ווערן באטראכט אַ ביינערי זוכן אויף די רעכט. וואָס איז דעם אופֿן איז? און ווי צו ינסטרומענט ביינערי זוכן? פּאַסקאַל איז די יזיאַסט סוויווע פֿאַר די אָרגאַניזאַציע פון אַזאַ אַ פּראָגראַם, אַזוי מיר וועט נוצן עס צו לערנען.

ערשטער, אַנאַלייז, וואָס זענען די אַדוואַנידזשיז פון דעם אופֿן, עס איז אַזוי מיר קענען פֿאַרשטיין, וואָס איז די פונט אין דעם לערנען פון דער טעמע. אַזוי, לאָזן ס האָבן אַ מענגע מיט אַ ויסמעסטונג פון לפּחות 100000000 עלעמענטן, וואָס דאַרפֿן צו געפֿינען עטלעכע. פון קורס, דעם פּראָבלעם קענען זיין לייכט סאַלווד דורך אַ פּשוט לינעאַר זוכן, אין וואָס מיר זענען ניצן די ציקל וועט פאַרגלייַכן די required עלעמענט מיט אַלע יענע וואס זענען אין די מענגע. די פּראָבלעם איז אַז די ימפּלאַמענטיישאַן פון דעם געדאַנק וועט נעמען צו פיל צייַט. אין אַ פּשוט פּאַסקאַל פּראָגראַם אין עטלעכע טריטמאַנץ, און דרייַ שורות פון די הויפּט טעקסט, איר וועט נישט באַמערקן עס, אָבער ווען מיר קומען צו אַ מער אָדער ווייניקער גרויס פּראַדזשעקס מיט אַ גרויס נומער פון צווייגן און גוט פונקטיאָנאַליטי, די פּראָגראַם וועט זיין גרייט צו זיין לאָודיד פֿאַר צו לאַנג. ספּעציעל אויב דער קאָמפּיוטער איז אַ שוואַך פאָרשטעלונג. דעריבער, עס איז אַ ביינערי זוכן, וואָס ראַדוסאַז זוכן צייַט לפּחות צוויי מאָל.

אזוי, וואָס איז די אַרבעט פּרינציפּ פון דעם אופֿן? מיד עס זאָל זאָגן אַז ביינערי זוכן אַרבעט איז נישט אין קיין מענגע, אָבער בלויז אויף אַ אויסגעשטעלט שטעלן פון נומערן. אין יעדער שריט גענומען מיטן עלעמענט פון די מענגע (טייַטש די נומער פון די עלעמענט). אויב די required נומער איז גרעסער ווי די דורכשניטלעך, דעריבער אַלע וואָס איז לינקס, אַז איז ווייניקער ווי די דורכשניטלעך צעל, קענען זיין דיסקאַרדיד און ניט צו קוקן דאָרט. קאָנווערסעלי, אויב ווייניקער ווי די דורכשניטלעך - צווישן די נומערן צו די רעכט, איר קענען ניט זוכן. דעמאָלט סעלעקטירן אַ נייַ זוכן געגנט, ווו דער ערשטער עלעמענט וועט זיין די מיטל עלעמענט פון די גאנצע מענגע, און די לעצטע און די לעצטע וועט. די דורכשניטלעך נומער פון נייַ פעלד וועט זיין אַ ¼ פון אַלע די אָפּשניט, וואָס איז, (די לעצטע עלעמענט + די מיטל עלעמענט פון די גאנצע מענגע) / 2. ווידער, די זעלבע אָפּעראַציע איז געטאן - אַ פאַרגלייַך מיט די דורכשניטלעך נומער פון די מענגע. אויב די ציל ווערט איז ווייניקער ווי די דורכשניטלעך, מיר אָפּוואַרפן די רעכט זייַט, און אויך צו טאָן ווייַטער, ביז איצט דעם מיטל עלעמענט וואָלט ניט געוואלט.

פון קורס, עס איז בעסטער צו קוקן אין אַ בייַשפּיל פון ווי צו שרייַבן ביינערי זוכן. פּאַסקאַל דאָ וועט פּאַסן ווער עס יז - ווערסיע איז ניט וויכטיק. זאל ס שרייַבן אַ פּשוט פּראָגראַם.

עס איז אַ מענגע פון 1 צו ה אונטער דעם נאָמען "מאַססיוו", אַ בייַטעוודיק ינדאַקייטינג דער נידעריקער גרענעץ פון די זוכן, גערופֿן "ניז", דער אויבערשטער שיעור, גערופֿן "ווערה", דער דורכשניטלעך זוכן טערמין - "סרעדן"; און די required נומער - "ISK".

אַזוי, ערשטער מיר באַשטימען דער אויבערשטער און נידעריקער שיעור פון די קייט זוכן:

ניז: = 1;
ווערה: = H + 1;

דעמאָלט אָרגאַניזירן די ציקל "ביז די דנאָ איז ווייניקער ווי דער אויבערשטער שיעור":

בשעת ניז <ווערה - 1 טאָן
אָנהייבן

אין יעדער שריט, מיר טיילן די אָפּשניט 2:

סרעדן: = (ניז, + ווערה) div 2; {ניצן די פֿונקציע div, ווייַל די טיילן אָן רעשט}

יעדער צייַט פון אָפּשאַצונג. ווייַל די נומער האט שוין געווען געפֿונען אויב די מיטל איז געוואלט, יבעררייַסן ציקל:

іף סרעדן = ISK דעמאָלט ברעכן;

אויב די מיטל עלעמענט פון די מענגע מער ווי געוואלט, אַוועקוואַרפן די לינקס זייַט, אַז איז, דער אויבערשטער גרענעץ פון די דורכשניטלעך נאָמינירן עלעמענט:

אויב מאַססיוו [סרעדן]> ISK דעמאָלט ווערה: = סרעדן;

און אויב אויף די פאַרקערט, עס מאכט דער נידעריקער גרענעץ:

אַנדערש ניז: = סרעדן;
סוף;

אַז ס אַלע אַז וועט זיין אין דעם פּראָגראַם.

זאל אונדז באַטראַכטן ווי עס וועט קוקן די ביינערי אופֿן אין פיר. באַטראַכטן דעם מענגע: 1, 3, 5, 7, 10, 12, 18 און עס וועט זוכן די נומער 12.

אין גאַנץ מיר האָבן 7 יסודות, אַזוי וועט די פערט מיטל, דער ווערט 7.

זינט מער ווי 12, 7, 1.3 און 5 עלעמענטן, מיר קענען אַוועקוואַרפן. דעמאָלט מיר ווע גאַט די נומער 4, 4/2 קיין רעזאַדו איז 2. אַזוי, אַ נייַ עלעמענט וועט זיין אַ דורכשניטלעך פון 10.

זינט 12 איז גרעסער ווי 10, מיר אַוועקוואַרפן 7. בלייבט נאָר 10, 12 און 18.

דאָ, די מיטל עלעמענט איז שוין 12, עס איז די required נומער. דעם אַרבעט איז געענדיקט - נומער 12 געפֿונען.