[Powered by Google Translate] [סעקשאַן 3 - מער באַקוועם] [ראָב באָוודען - האַרוואַרד אוניווערסיטעט] 

[דאס איז קס50. - CS50.TV] 

אַזוי דער ערשטער קשיא איז סטריינדזשלי ווערדיד. גדב לעץ איר "דעבוג" אַ פּראָגראַם, אָבער, מער ספּאַסיפיקלי, וואָס טוט עס לאָזן איר טאָן? איך וועט ענטפֿערן אַז איינער, און איך טאָן ניט וויסן וואָס ס פּונקט דערוואַרט, אַזוי איך בין געסינג עס ס 'עפּעס צוזאמען די שורות פון עס לעץ איר שריט דורך שריט גיין דורך די פּראָגראַם, ינטעראַקט מיט עס, טוישן וועריאַבאַלז, טאָן אַלע די זאכן - בייסיקלי גאָר קאָנטראָל דורכפירונג פון אַ פּראָגראַם און דורכקוקן קיין געגעבן טייל פון דער דורכפירונג פון דער פּראָגראַם. אַזוי יענע פֿעיִקייטן לאָזן איר דעבוג זאכן. אָוקיי. וואָס טוט ביינערי זוכן דאַרפן אַז אַ מענגע זייַן אויסגעשטעלט? ווער וויל צו ענטפֿערן וואָס? [תּלמיד] ווייַל עס טוט נישט אַרבעטן אויב עס ס נישט אויסגעשטעלט. >> יאָ. [געלעכטער] אויב עס ס נישט אויסגעשטעלט, דעמאָלט עס ס אוממעגלעך צו שפּאַלטן עס אין העלפט און וויסן אַז אַלץ צו דער לינקס איז ווייניקער און אַלץ צו די רעכט איז גרעסער ווי די מיטל ווערט. אַזוי עס דאַרף צו זייַן אויסגעשטעלט. אָוקיי. פארוואס איז בלאָז סאָרט אין אָ פון N סקווערד? טוט ווער עס יז ערשטער ווילן צו געבן אַ זייער שנעל הויך-מדרגה איבערבליק פון וואָס בלאָז סאָרט איז? [תּלמיד] איר בייסיקלי גיין דורך יעדער עלעמענט און איר טשעק דער ערשטער ביסל עלעמענטן. אויב זיי ניטאָ אויס פון ווו איר ויסבייַטן זיי, דעריבער איר טשעק דער ווייַטער ביסל יסודות און אַזוי אויף. ווען איר דערגרייכן די סוף, דעמאָלט איר וויסן אַז דער גרעסטער עלעמענט איז געשטעלט אין די סוף, אַזוי איר איגנאָרירן אַז מען דעמאָלט איר האַלטן אויף געגאנגען דורך, און יעדער צייַט איר האָבן צו קאָנטראָלירן איינער ווייניקער עלעמענט ביז איר מאַכן קיין ענדערונגען. >> יאָ. עס ס גערופן בלאָז סאָרט ווייַל אויב איר פליפּ די מענגע אויף זייַן זייַט אַזוי עס ס אַרויף און אַראָפּ, ווערטיקאַל, דעריבער די גרויס וואַלועס וועט זינקען צו די דנאָ און די קליין וואַלועס וועט בלאָז אַרויף צו די שפּיץ. אַז ס ווי עס גאַט זייַן נאָמען. און יאָ, איר נאָר גיין דורך. איר האַלטן געגאנגען דורך די מענגע, סוואַפּינג די גרעסערע ווערט צו באַקומען די גרעסטע וואַלועס צו די דנאָ. 

פארוואס איז עס אָ פון N סקווערד? ערשטער, טוט ווער עס יז ווילן צו זאָגן וואָס עס ס אָ פון N סקווערד? [תּלמיד] ווייַל פֿאַר יעדער לויפן עס גייט N מאל. איר קענען נאָר זייַן זיכער אַז איר ווע גענומען די ביגאַסט עלעמענט אַלע די וועג אַראָפּ, דעמאָלט איר האָבן צו איבערחזרן אַז פֿאַר ווי פילע עלעמענטן. >> יאָ. אַזוי האַלטן אין גייַסט וואָס גרויס אָ מיטל און וואָס גרויס תוו מיטל. די גרויס אָ איז ווי דער אויבערשטער געבונדן אויף ווי פּאַמעלעך עס קענען פאקטיש לויפן. אַזוי דורך זאגן עס ס אָ פון N סקווערד, עס איז נישט אָ פון N אָדער אַנדערש עס וואָלט זייַן ביכולת צו לויפן אין לינעאַר צייַט, אָבער עס איז אָ פון N קיובד ווייַל עס איז באַונדאַד דורך אָ פון N קיובד. אויב עס ס באַונדאַד דורך אָ פון N סקווערד, דעמאָלט עס ס באַונדאַד אויך דורך N קיובד. אַזוי עס איז N סקווערד, און אין די אַבסאָלוט ערגסט פאַל עס קענען נישט טאָן בעסער ווי N סקווערד, וואָס איז וואָס עס ס אָ פון N סקווערד. אַזוי צו זען קליין מאַט אין ווי עס קומט אויס צו זייַן N סקווערד, אויב מיר האָבן פינף זאכן אין אונדזער רשימה, די ערשטער מאָל ווי פילע סוואַפּס קען מיר פּאַטענטשאַלי דאַרפֿן צו מאַכן אין סדר צו באַקומען דעם? זאל ס 'פאקטיש פּונקט - ווי פילע סוואַפּס זענען מיר געגאנגען צו האָבן צו מאַכן אין דער ערשטער לויפן פון בלאָז סאָרט דורך די מענגע? [תּלמיד] N - 1. >> יאָ. 

אויב עס זענען 5 עלעמענטן, מיר רע געגאנגען צו דאַרפֿן צו מאַכן N - 1. דעמאָלט אויף די רגע איינער ווי פילע סוואַפּס זענען מיר געגאנגען צו האָבן צו מאַכן? [תּלמיד] N - 2. >> יאָ. און די דריט איז געגאנגען צו זייַן N - 3, און דעמאָלט פֿאַר קאַנוויניאַנס איך וועל שרייַבן די לעצטע צוויי ווי דעמאָלט מיר רע געגאנגען צו דאַרפֿן צו מאַכן 2 סוואַפּס און 1 ויסבייַטן. איך טרעפן די לעצטע איינער זאל אָדער זאל נישט פאקטיש דאַרפֿן צו פּאַסירן. איז עס אַ ויסבייַטן? איך טאָן ניט וויסן. אַזוי די ביסט די גאַנץ אַמאַונץ פון סוואַפּס אָדער בייַ מינדסטער קאַמפּעראַסאַנז איר האָבן צו מאַכן. אפילו אויב איר טאָן ניט ויסבייַטן, איר נאָך דאַרפֿן צו פאַרגלייַכן די וואַלועס. אַזוי עס זענען N - 1 קאַמפּעראַסאַנז אין דער ערשטער לויפן דורך די מענגע. אויב איר ריעריינדזש די זאכן, לאָזן ס פאקטיש מאַכן עס זעקס זאכן אַזוי דאס אָנלייגן אַרויף נייסלי, און דעמאָלט איך וועט טאָן 3, 2, 1. אַזוי נאָר ריעריינדזשינג די סאַמז, מיר ווילן צו זען ווי פילע קאַמפּעראַסאַנז מיר מאַכן אין די גאנצע אַלגערידאַם. אַזוי אויב מיר ברענגען די גייז אַראָפּ דאָ, דעמאָלט מיר ניטאָ נאָך נאָר סאַמינג אָבער פילע קאַמפּעראַסאַנז דאָרט געווען. אבער אויב מיר סאַכאַקל די און מיר סאַכאַקל די און מיר סאַכאַקל די, עס ס נאָך די זעלבע פּראָבלעם. מיר נאָר סאַכאַקל יענע באַזונדער גרופּעס. 

אַזוי איצט מיר רע סאַמינג 3 N ס. עס ס נישט נאָר 3 N ס. עס ס שטענדיק געגאנגען צו זייַן N / 2 N ס. אַזוי דאָ מיר פּאַסירן צו האָבן 6. אויב מיר האט 10 זאכן, דעריבער מיר קען טאָן דעם גרופּינג פֿאַר 5 פאַרשידענע פּערז פון זאכן און סוף אַרויף מיט N + N + N + N + N. אַזוי איר ניטאָ שטענדיק געגאנגען צו באַקומען N / 2 N ס, און אַזוי דאָס מיר וועט דזשאַט עס אויס צו N סקווערד / 2. און אַזוי אַפֿילו כאָטש עס ס דער פאַקטאָר פון העלפט, וואָס כאַפּאַנז צו קומען אין ווייַל פון די פאַקט אַז דורך יעדער יטעראַטיאָן איבער די מענגע מיר פאַרגלייַכן 1 ווייניקער אַזוי אַז ס ווי מיר באַקומען די איבער 2, אָבער עס איז נאָך N סקווערד. מיר טאָן ניט זאָרגן וועגן די קעסיידערדיק פאַקטאָר פון אַ האַלב. אַזוי אַ פּלאַץ פון גרויס אָ שטאָפּן ווי דעם רעליעס אויף נאָר מין פון טאן דעם סאָרט פון מאַט, טאן אַריטמעטיק סאַמז און דזשיאַמעטריק סעריע שטאָפּן, אָבער רובֿ פון זיי אין דעם קורס זענען שיין סטרייטפאָרווערד. אָוקיי. פארוואס איז ינסערשאַן סאָרט אין תוו פון ען? וואָס טוט תוו מיינען? [צוויי סטודענטן גערעדט בייַ אַמאָל - אַנינטעלאַדזשאַבאַל] >> יאָ. תוו איר קענען טראַכטן פון ווי דער נידעריקער געבונדן. 

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

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

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

טוט ווער עס יז ווילן צו נאָר געבן אַ פּסעודאָקאָדע הויך-מדרגה דערקלערונג פון וואָס מיר רע געגאנגען צו האָבן צו טאָן פֿאַר זוכן? יאָ. [תּלמיד] איר נאָר נעמען די מיטן פון די מענגע און זען אויב וואָס איר ניטאָ קוקן פֿאַר איז ווייניקער ווי אַז אָדער מער ווי אַז. און אויב עס ס ווייניקער, איר גיין צו די העלפט אַז ס ווייניקער, און אויב עס ס 'מער, איר גיין צו די העלפט אַז ס מער און איר איבערחזרן אַז ביז איר נאָר באַקומען איין זאַך. [באָוודען] יאָ. נאָטיץ אַז אונדזער נומערן מענגע איז שוין אויסגעשטעלט, און אַזוי אַז מיטל וואָס מיר קענען נעמען מייַלע פון ​​וואָס און מיר קען ערשטער טשעק, אָוקיי, איך בין קוקן פֿאַר די נומער 50. אַזוי איך קענען גיין אין דער מיטן. מיטל איז שווער צו דעפינירן ווען עס ס אַן אַפֿילו נומער פון זאכן, אָבער לאָזן ס נאָר זאָגן מיר וועט שטענדיק טראַנגקייט צו די מיטל. אַזוי דאָ מיר האָבן 8 זאכן, אַזוי די מיטל וואָלט זייַן 16. איך בין קוקן פֿאַר 50, אַזוי 50 איז גרעסער ווי 16. אַזוי איצט איך קענען בייסיקלי מייַכל מיין מענגע ווי די יסודות. איך קענען וואַרפן אַוועק אַלץ פון 16 איבער. איצט מיין מענגע איז נאָר די 4 יסודות, און איך איבערחזרן. אַזוי דעמאָלט איך ווילן צו געפֿינען די מיטל ווידער, וואָס איז געגאנגען צו זייַן 42. 42 איז ווייניקער ווי 50, אַזוי איך קענען וואַרפן אַוועק די צוויי יסודות. דאס איז מיין רוען מענגע. איך בין געגאנגען צו געפֿינען די מיטל ווידער. איך טרעפן 50 איז געווען אַ שלעכט בייַשפּיל ווייַל איך איז געווען שטענדיק פארווארפן אַוועק זאכן צו די לינקס, אָבער דורך די זעלבע מאָס, אויב איך בין קוקן פֿאַר עפּעס און עס ס ווייניקער ווי די עלעמענט איך בין דערווייַל קוקן בייַ, דעמאָלט איך בין געגאנגען צו וואַרפן אַוועק אַלץ צו די רעכט. אַזוי איצט מיר דאַרפֿן צו מאַכשער אַז. נאָטיץ אַז מיר דאַרפֿן צו פאָרן אין גרייס. מיר קענען אויך ניט דאַרפֿן צו שווער-קאָד גרייס. אַזוי אויב מיר באַקומען באַפרייַען פון וואָס # דעפינירן - אָוקיי. ווי קענען איך נייסלי רעכענען אויס וואָס די גרייס פון די נומערן מענגע דערווייַל איז? 

ווי פילע עלעמענטן זענען אין די נומערן מענגע? [תּלמיד] נומערן, בראַקאַץ,. לענג? [באָוודען] אַז טוט נישט עקסיסטירן אין סי דאַרפֿן. לענג. ערייז טאָן ניט האָבן פּראָפּערטיעס, אַזוי עס איז ניט לענג פאַרמאָג פון ערייז אַז וועט נאָר געבן איר אָבער לאַנג עס כאַפּאַנז צו זייַן. [תּלמיד] זען ווי פיל זכּרון עס האט און טיילן דורך ווי פיל - >> יאָ. אַזוי ווי קענען מיר זען ווי פיל זכּרון עס האט? >> [תּלמיד] סיזעאָף. >> יאָ, סיזעאָף. סיזעאָף איז דער אָפּעראַטאָר אַז ס 'געגאנגען צו צוריקקומען די גרייס פון די נומערן מענגע. און אַז ס 'געגאנגען צו זייַן אָבער פילע ינטאַדזשערז עס זענען מאל די גרייס פון אַ ינטעגער זינט אַז ס ווי פיל זכּרון עס ס 'פאקטיש גענומען אַרויף. אַזוי אויב איך ווילן די נומער פון זאכן אין די מענגע, דעמאָלט איך בין געגאנגען צו ווילן צו טיילן דורך די גרייס פון אַ ינטעגער. אָוקיי. אַזוי אַז לעץ מיר פאָרן אין גרייס דאָ. פארוואס טאָן איך דאַרפֿן צו פאָרן אין גרייס אין אַלע? פארוואס קענען ניט איך נאָר טאָן אַרויף דאָ ינט גרייס = סיזעאָף (כייסטאַק) / סיזעאָף (ינט)? פארוואס טוט דאָס נישט אַרבעטן? [תּלמיד] עס ס נישט אַ גלאבאלע בייַטעוודיק. [באָוודען] הייַסטאַקק יגזיסץ און מיר רע גייט פארביי אין נומערן ווי כייסטאַק, און דאָס איז מין פון אַ פאָרשאַדאָוינג פון וואָס ס צו קומען. יאָ. [תּלמיד] הייַסטאַקק איז נאָר די דערמאָנען צו עס, אַזוי עס וואָלט צוריקקומען ווי גרויס אַז דערמאָנען איז. יאָ. איך צווייפל אין לעקציע אַז איר ווע געזען דעם אָנלייגן נאָך טאַקע, רעכט? מיר ווע נאָר גערעדט וועגן אים. אַזוי דעם אָנלייגן איז ווו אַלע פון ​​דיין וועריאַבאַלז זענען געגאנגען צו זייַן סטאָרד. 

קיין זכּרון אַז ס אַלאַקייטיד פֿאַר היגע וועריאַבאַלז איז געגאנגען אין דעם אָנלייגן, און יעדער פֿונקציע געץ זייַן אייגן פּלאַץ אויף די אָנלייגן, זייַן אייגן אָנלייגן ראַם איז וואָס עס ס גערופן. אַזוי הויפּט האט זייַן אָנלייגן ראַם, און ין פון עס איז געגאנגען צו עקזיסטירן דעם נומערן מענגע, און עס ס געגאנגען צו זייַן פון גרייס סיזעאָף (נומערן). עס ס געגאנגען צו האָבן גרייס פון נומערן צעטיילט דורך גרייס פון עלעמענטן, אָבער אַז אַלע לעבן ין הויפּט ס אָנלייגן ראַם. ווען מיר רופן זוכן, זוכן געץ זייַן אייגן אָנלייגן ראַם, זייַן אייגן פּלאַץ צו קראָם אַלע פון ​​זייַן היגע וועריאַבאַלז. אבער די טענות - אַזוי כייסטאַק איז נישט אַ קאָפּיע פון ​​דעם גאנצע מענגע. מיר טאָן נישט פאָרן אין די גאנצע מענגע ווי אַ קאָפּיע אין זוכן. עס נאָר פּאַסיז אַ דערמאָנען צו אַז מענגע. אַזוי זוכן קענען צוטריט די נומערן דורך דעם דערמאָנען. עס ס נאָך אַקסעסינג די זאכן וואָס לעבן ין פון הויפּט ס אָנלייגן ראַם, אָבער בייסיקלי, ווען מיר באַקומען צו פּוינטערז, וואָס זאָל זייַן באַלד, דאָס איז וואָס פּוינטערז זענען. פּאָינטערס זענען נאָר באַווייַזן צו זאכן, און איר קענען נוצן פּוינטערז צו צוטריט זאכן וואָס זענען אין אנדערע זאכן 'אָנלייגן ראָמען. אַזוי אַפֿילו כאָטש נומערן איז היגע צו הויפּט, מיר קענען נאָך צוטריט עס דורך דעם טייַטל. אבער זינט עס ס נאָר אַ טייַטל און עס ס נאָר אַ דערמאָנען, סיזעאָף (כייסטאַק) נאָר קערט די גרייס פון דעם דערמאָנען זיך. עס טוט נישט צוריקקומען די גרייס פון דער זאַך עס ס פּוינטינג צו. עס טוט נישט צוריקקומען די פאַקטיש גרייס פון נומערן. און אַזוי דאָס איז נישט געגאנגען צו אַרבעטן ווי מיר ווילן עס צו. 

שאלות אויף וואָס? פּאָינטערס וועט זייַן ניטאָ אין אין באטייטיק מער גאָרי דעטאַל אין וואָכן צו קומען. און דאָס איז וואָס אַ פּלאַץ פון זאכן וואָס איר זען, רובֿ זוכן זאכן אָדער סאָרט זאכן, זיי ניטאָ כּמעט אַלע געגאנגען צו דאַרפֿן צו נעמען די פאַקטיש גרייס פון דער מענגע, ווייַל אין C, מיר האָבן קיין געדאַנק וואָס די גרייס פון דעם מענגע איז. איר דאַרפֿן צו מאַניואַלי פאָרן עס ין און איר קענען נישט מאַניואַלי פאָרן אין די גאנצע מענגע ווייַל איר ניטאָ נאָר גייט פארביי אין די דערמאָנען און עס קען נישט באַקומען די גרייס פון דעם דערמאָנען. אָוקיי. אַזוי איצט מיר ווילן צו מאַכשער וואָס איז דערקלערט פריער. איר קענען אַרבעטן אויף עס פֿאַר אַ מינוט, און איר טאָן ניט האָבן צו זאָרג וועגן געטינג אַלץ בישליימעס 100% ארבעטן. נאָר שרייַבן אַרויף די האַלב פּסעודאָקאָדע פֿאַר ווי איר טראַכטן עס זאָל אַרבעטן. אָוקיי. ניט דאַרפֿן צו זייַן גאָר געטאן מיט דעם נאָך. אבער טוט ווער עס יז פילן באַקוועם מיט וואָס זיי האָבן אַזוי ווייַט, ווי עפּעס מיר קענען אַרבעטן מיט צוזאַמען? טוט ווער עס יז ווילן צו פרייַוויליקער? אָדער איך וועל ראַנדאַמלי קלייַבן. עס טוט נישט האָבן צו זייַן רעכט דורך קיין מאָס אָבער עפּעס מיר קענען מאָדיפיצירן אין אַ ארבעטן שטאַט. [תּלמיד] זיכער. >> אָוקיי. אַזוי קענען איר ראַטעווען די רעוויזיע דורך געבן אַ קליק אויף די ביסל היט בילדל. איר רע ראַמיאַ, רעכט? >> [תּלמיד] יאָ. >> [באָוודען] אָוקיי. אַזוי איצט איך קענען קוק דיין רעוויזיע און אַלעמען קענען ציען אַרויף די רעוויזיע. און דאָ מיר האָבן - אָוקיי. אַזוי ראַמיאַ געגאנגען מיט די רעקורסיווע לייזונג, וואָס איז באשטימט אַ גילטיק לייזונג. עס זענען צוויי וועגן איר קענען טאָן דעם פּראָבלעם. איר קענען אָדער טאָן עס יטעראַטיוועלי אָדער רעקורסיוועלי. רובֿ פּראָבלעמס איר טרעפן וואָס קענען זייַן געטאן רעקורסיוועלי קענען אויך זייַן געטאן יטעראַטיוועלי. אַזוי דאָ מיר ווע געטאן עס רעקורסיוועלי. 

טוט עמעצער ווילן צו דעפינירן וואָס עס מיטל צו מאַכן אַ פֿונקציע רעקורסיווע? [תּלמיד] ווען איר האָט אַ פֿונקציע רופן זיך און דעמאָלט רופן זיך ביז עס קומט אויס מיט אמת און אמת. >> יאָ. א רעקורסיווע פֿונקציע איז נאָר אַ פֿונקציע וואָס רופט זיך. עס זענען דרייַ גרויס זאכן וואָס אַ רעקורסיווע פונקציאָנירן מוזן האָבן. דער ערשטער איז דאָך, עס רופט זיך. די רגע איז די באַזע פאַל. אַזוי בייַ עטלעכע פונט די פֿונקציע דאַרף צו האַלטן פאַך זיך, און אַז ס וואָס די באַזע פאַל איז פֿאַר. אַזוי דאָ מיר וויסן אַז מיר זאָל האַלטן, מיר זאָל געבן אַרויף אין אונדזער זוכן ווען אָנהייב יקוואַלז סוף - און מיר וועט גיין איבער וואָס אַז מיטל. אבער לעסאָף, די לעצטע זאַך וואָס ס וויכטיק פֿאַר רעקורסיווע פאַנגקשאַנז: די פאַנגקשאַנז מוזן עפעס צוגאַנג די באַזע פאַל. ווי אויב איר ניטאָ נישט פאקטיש אַפּדייטינג עפּעס ווען איר מאַכן די רגע רעקורסיווע רופן, אויב איר רע ממש נאָר פאַך די פֿונקציע ווידער מיט די זעלבע טענות און קיין גלאבאלע וועריאַבאַלז האָבן געביטן אָדער עפּעס, איר וועט קיינמאָל דערגרייכן די באַזע פאַל, אין וועלכע פאַל אַז ס 'שלעכט. עס וועט זייַן אַ ינפאַנאַט רעקורסיאָן און אַ אָנלייגן לויפן. אבער דאָ מיר זען אַז דער דערהייַנטיקן איז געשעעניש זינט מיר זענען אַפּדייטינג אָנהייב + סוף / 2, מיר רע אַפּדייטינג דער סוף אַרגומענט דאָ, מיר רע אַפּדייטינג די אָנהייב אַרגומענט דאָ. אַזוי אין אַלע רעקורסיווע רופט מיר זענען אַפּדייטינג עפּעס. אָוקיי. צי איר ווילן צו גיין אונדז דורך דיין לייזונג? >> זיכער. איך בין ניצן סעאַרטשהעלפּ אַזוי אַז יעדער מאָל איך מאַכן דעם פֿונקציע רופן איך האָבן די אָנהייב פון ווו איך בין קוקן פֿאַר אין די מענגע און דער סוף פון ווו איך בין קוקן די מענגע. 

אין יעדער שריט ווו עס ס זאגן עס ס די מיטל עלעמענט, וואָס איז אָנהייב + סוף / 2, איז אַז גלייַך צו וואָס מיר רע קוקן פֿאַר? און אויב עס איז, דעריבער מיר געפונען עס, און איך טרעפן אַז געץ דורכגעגאנגען אַרויף די לעוועלס פון רעקורסיאָן. און אויב אַז ס 'נישט אמת, דעמאָלט מיר קאָנטראָלירן צי אַז מיטן ווערט פון די מענגע איז אויך גרויס, אין וואָס פאַל מיר קוקן אין די לינקס האַלב פון די מענגע דורך געגאנגען פון אָנהייב צו די מיטל אינדעקס. און אַנדערש מיר טאָן די סוף האַלב. [באָוודען] אָוקיי. אַז סאָונדס גוט. אָוקיי, אַזוי אַ פּאָר זאכן, און פאקטיש, דאָס איז אַ זייער הויך-מדרגה זאַך אַז איר וועט קיינמאָל דאַרפֿן צו וויסן פֿאַר דעם קורס, אָבער עס איז אמת. רעקורסיווע פאַנגקשאַנז, איר שטענדיק הערן אַז זיי ניטאָ אַ שלעכט האַנדלען ווייַל אויב איר רעקורסיוועלי רופן זיך אויך פילע מאל, איר באַקומען אָנלייגן לויפן זינט, ווי איך געזאגט פריער, יעדער פֿונקציע געץ זייַן אייגן אָנלייגן ראַם. אַזוי יעדער רופן פון די רעקורסיווע פונקציאָנירן געץ זייַן אייגן אָנלייגן ראַם. אַזוי אויב איר מאַכן 1.000 רעקורסיווע רופט, איר באַקומען 1.000 אָנלייגן ראָמען, און געשווינד איר פירן צו ווייל אויך פילע אָנלייגן ראָמען און דאס נאָר ברעכן. אַזוי אַז ס וואָס רעקורסיווע פאַנגקשאַנז זענען בכלל שלעכט. אבער עס איז אַ פייַן סאַבסעט פון רעקורסיווע פאַנגקשאַנז גערופן עק-רעקורסיווע פאַנגקשאַנז, און דעם כאַפּאַנז צו זייַן אַ בייַשפּיל פון איין ווו אויב דער קאַמפּיילער נאטיצן דעם און עס זאָל, איך טראַכטן - אין קלאַנג אויב איר פאָרן עס דער-2 פאָן דעמאָלט עס וועט באַמערקן דעם איז עק רעקורסיווע און מאַכן דאס גוט. 

עס וועט רייוס דער זעלביקער אָנלייגן ראַם איבער און איבער ווידער פֿאַר יעדער רעקורסיווע רופן. און אַזוי זינט איר ניטאָ ניצן די זעלבע אָנלייגן ראַם, איר טאָן ניט דאַרפֿן צו זאָרג וועגן אלץ אָנלייגן איבערפולט, און אין דער זעלביקער צייַט, ווי איר האט געזאגט פריער, ווו אַמאָל איר צוריקקומען אמת, דעמאָלט עס האט צו צוריקקומען אַרויף אַלע פון ​​די אָנלייגן ראָמען און די 10 רופן צו סעאַרטשהעלפּ האט צו צוריקקומען צו די 9, האט צו צוריקקומען צו די 8. אַזוי אַז טוט נישט דאַרפֿן צו פּאַסירן ווען פאַנגקשאַנז זענען עק רעקורסיווע. און אַזוי וואָס מאכט דעם פֿונקציע עק רעקורסיווע איז באַמערקן אַז פֿאַר קיין געגעבן רופן צו סעאַרטשהעלפּ די רעקורסיווע רופן אַז עס ס געמאכט איז וואָס עס ס אומגעקערט. אַזוי אין דער ערשטער רופן צו סעאַרטשהעלפּ, מיר אָדער תיכף צוריקקומען פאַלש, תיכף צוריקקומען אמת, אָדער מיר מאַכן אַ רעקורסיווע רופן צו סעאַרטשהעלפּ ווו וואָס מיר רע אומגעקערט איז וואָס אַז רופן איז אומגעקערט. און מיר קען נישט טאָן דעם אויב מיר האט עפּעס ווי ינט X = סעאַרטשהעלפּ, צוריקקומען X * 2, נאָר עטלעכע טראַפ טוישן. 

אַזוי איצט דעם רעקורסיווע רופן, דאָס ינט X = סעאַרטשהעלפּ רעקורסיווע רופן, איז ניט מער עק רעקורסיווע ווייַל עס פאקטיש טוט האָבן צו צוריקקומען צוריק צו אַ פֿריִערדיקע אָנלייגן ראַם אַזוי אַז אַז פֿריִערדיקע רופן צו די פֿונקציע קענען דעמאָלט טאָן עפּעס מיט די צוריקקומען ווערט. אַזוי דעם איז ניט עק רעקורסיווע, אָבער וואָס מיר האבן פריער איז נייסלי עק רעקורסיווע. יאָ. [תּלמיד] זאָל ניט די רגע באַזע פאַל זייַן אָפּגעשטעלט ערשטער ווייַל דאָרט קען זייַן אַ סיטואַציע ווו ווען איר פאָרן עס די אַרגומענט איר האָבן אָנהייב = סוף, אָבער זיי זענען די נאָדל ווערט. די קשיא איז געווען קענען נישט מיר לויפן אין דעם פאַל ווו סוף איז דער נאָדל ווערט אָדער אָנהייב = סוף, אַפּראָופּרייטלי, אָנהייב = סוף און איר האָט נישט פאקטיש אָפּגעשטעלט אַז באַזונדער ווערט נאָך, דעמאָלט אָנהייב + סוף / 2 איז נאָר געגאנגען צו זייַן די זעלבע ווערט. אבער מיר 'ווע שוין אומגעקערט פאַלש און מיר קיינמאָל פאקטיש אָפּגעשטעלט די ווערט. אַזוי בייַ די זייער מינדסטער, אין דער ערשטער רופן, אויב גרייס איז 0, דעמאָלט מיר ווילן צו צוריקקומען פאַלש. אבער אויב גרייס איז 1, דעמאָלט אָנהייב איז נישט געגאנגען צו גלייַך סוף, און מיר וועט בייַ מינדסטער טשעק די איין עלעמענט. אבער איך טראַכטן איר זענט רעכט אין וואָס מיר קענען סוף אַרויף אין אַ פאַל ווו אָנהייב + סוף / 2, אָנהייב ענדס אַרויף זייַענדיק די זעלבע ווי אָנהייב + סוף / 2, אָבער מיר קיינמאָל פאקטיש אָפּגעשטעלט אַז עלעמענט. 

אַזוי אויב מיר ערשטער טשעק איז דער מיטל עלעמענט דער ווערט מיר רע קוקן פֿאַר, דעמאָלט מיר קענען תיכף צוריקקומען אמת. אַנדערש אויב זיי ניטאָ גלייַך, דעמאָלט דאָרט ס קיין פונט אין ממשיך זינט מיר רע נאָר געגאנגען צו דערהייַנטיקן צו אַ פאַל ווו מיר זענען אויף אַ איין-עלעמענט מענגע. אויב אַז איין עלעמענט איז נישט דער איינער מיר רע קוקן פֿאַר, דעריבער אַלץ איז פאַלש. יאָ. [תּלמיד] די זאַך איז אַז זינט גרייס איז פאקטיש גרעסערע ווי די נומער פון עלעמענטן אין דער מענגע, עס איז שוין אַ פאָטאָ - >> אזוי וועט גרייס - [תּלמיד] זאָגן אויב די מענגע איז גרייס 0, דעמאָלט דער סעאַרטשהעלפּ וועט פאקטיש טשעק כייסטאַק פון 0 אויף דער ערשטער רופן. די מענגע האט גרייס 0, אַזוי דער 0 איז - >> יאָ. עס ס אן אנדער זאַך וואָס - עס זאל זייַן גוט. זאל ס טראַכטן. אַזוי אויב דער מענגע האט 10 יסודות און דעם מיטל איינער מיר רע געגאנגען צו קאָנטראָלירן איז אינדעקס 5, אַזוי מיר רע קאָנטראָלירונג 5, און לאָזן 'ס זאָגן אַז די ווערט איז ווייניקער. אַזוי מיר רע פארווארפן אַלץ אַוועק פון 5 פאָרויס. אַזוי אָנהייבן + סוף / 2 איז געגאנגען צו זייַן אונדזער נייַ סוף, אַזוי יאָ, עס ס שטענדיק געגאנגען צו בלייַבן ווייַטער פון די סוף פון די מענגע. אויב עס ס אַ פאַל אויב עס איז אַפֿילו אָדער מאָדנע, דעמאָלט מיר וואָלט טשעק, זאָגן, 4, אָבער מיר ניטאָ נאָך פארווארפן אַוועק - אַזוי יאָ, סוף איז שטענדיק געגאנגען צו זייַן ווייַטער פון די פאַקטיש סוף פון די מענגע. אַזוי די יסודות מיר זענען פאָוקיסינג אויף, סוף איז שטענדיק געגאנגען צו זייַן די מען נאָך אַז. און אַזוי אויב אָנהייב טוט אלץ גלייַך סוף, מיר זענען אין אַ מענגע פון ​​גרייס 0. 

די אנדערע זאַך איך איז געווען טראכטן איז מיר זענען אַפּדייטינג אָנהייבן צו זייַן אָנהייב + סוף / 2, אַזוי דאָס איז די פאַל וואָס איך בין בעת ​​צרה מיט, ווו אָנהייב + סוף / 2 איז דער עלעמענט מיר רע קאָנטראָלירונג. זאל ס זאָגן מיר האט דעם 10-עלעמענט מענגע. וועלכער. אַזוי אָנהייבן + סוף / 2 איז געגאנגען צו זייַן עפּעס ווי דאָס איינער, און אויב אַז ס ניט די ווערט, זאָגן מיר ווילן צו דערהייַנטיקן. די ווערט איז גרעסער, אַזוי מיר ווילן צו קוקן אין דעם האַלב פון די מענגע. אַזוי ווי מיר רע אַפּדייטינג אָנהייב, מיר רע אַפּדייטינג אָנהייבן צו איצט זייַן דעם עלעמענט. אבער דאָס קען נאָך אַרבעט, אָדער בייַ די זייער מינדסטער, איר קענען טאָן אָנהייב + סוף / 2 + 1. [תּלמיד] איר טאָן ניט דאַרפֿן צו זייַן אָנהייב + סוף [ינאָדאַבאַל] >> יאָ. מיר האָבן שוין אָפּגעשטעלט דעם עלעמענט און וויסן עס ס 'נישט דער איינער מיר רע קוקן פֿאַר. אַזוי מיר טאָן ניט דאַרפֿן צו דערהייַנטיקן אָנהייבן צו זייַן דעם עלעמענט. מיר קענען נאָר האָפּקען עס און דערהייַנטיקן אָנהייבן צו זייַן דעם עלעמענט. און איז עס אלץ אַ פאַל, לאָזן ס זאָגן, אַז דאָס זענען געווען סוף, אַזוי דאַן אָנהייבן וואָלט זייַן דעם, אָנהייב + סוף / 2 וואָלט זייַן דעם, אָנהייב + סוף - יאָ, איך טראַכטן עס קענען סוף אַרויף אין ינפאַנאַט רעקורסיאָן. זאל ס זאָגן עס ס נאָר אַ מענגע פון ​​גרייס 2 אָדער אַ מענגע פון ​​נומער 1. איך טראַכטן דאָס וועט אַרבעטן. אַזוי דערווייַל, אָנהייב איז אַז עלעמענט און סוף איז 1 ווייַטער פון אים. אַזוי דער עלעמענט וואָס מיר רע געגאנגען צו קאָנטראָלירן איז דאָס איינער, און דעריבער ווען מיר דערהייַנטיקן אָנהייב, מיר רע אַפּדייטינג אָנהייבן צו זייַן 0 + 1/2, וואָס איז געגאנגען צו סוף אונדז צוריק מיט אָנהייב זייַענדיק דעם עלעמענט. 

אַזוי מיר רע קאָנטראָלירונג דער זעלביקער עלעמענט איבער און איבער ווידער. אַזוי דאָס איז די פאַל ווו יעדער רעקורסיווע רופן מוזן פאקטיש דערהייַנטיקן עפּעס. אַזוי מיר דאַרפֿן צו טאָן אָנהייב + סוף / 2 + 1, אָדער אַנדערש דאָרט ס אַ פאַל ווו מיר רע נישט פאקטיש אַפּדייטינג אָנהייב. אַלעמען זען וואָס? אָוקיי. טוט ווער עס יז האָבן שאלות אויף דעם לייזונג אָדער קיין מער באַמערקונגען? אָוקיי. טוט ווער עס יז האָבן אַ יטערייטיוו לייזונג אַז מיר קענען אַלע קוקן בייַ? האט מיר אַלע טאָן עס רעקורסיוועלי? אָדער אויך איך טרעפן אויב איר געעפנט הערס, דעמאָלט איר זאל האָבן אָווועררידאַן דיין פֿריִערדיקע איינער. טוט עס אויטאָמאַטיש היט? איך בין נישט positive. טוט ווער עס יז האָבן יטערייטיוו? מיר קענען גיין דורך עס צוזאַמען אויב נישט. דער געדאַנק איז געגאנגען צו זייַן די זעלבע. יטעראַטיווע לייזונג. מיר רע געגאנגען צו ווילן צו בייסיקלי טאָן די זעלבע געדאַנק ווו מיר ווילן צו האַלטן שפּור פון די נייַ סוף פון די מענגע און די נייַ אָנהייב פון די מענגע און טאָן אַז איבער און איבער. און אויב וואָס מיר רע בעכעסקעם שפּור פון ווי דער אָנהייב און דער סוף אלץ ינטערסעקט, דעמאָלט מיר האט ניט געפֿינען עס און מיר קענען צוריקקומען פאַלש. אַזוי ווי טאָן איך טאָן אַז? ווער עס יז האָבן פֿירלייגן אָדער קאָד פֿאַר מיר צו ציען אַרויף? [תּלמיד] צי אַ בשעת שלייף. >> יאָ. איר זענט געגאנגען צו ווילן צו טאָן אַ שלייף. 

האט איר האָבן קאָד איך קען ציען אַרויף, אָדער וואָס זענען איר געגאנגען צו פֿאָרשלאָגן? [תּלמיד] איך טראַכטן אַזוי. >> אַלע רעכט. דאס מאכט דאס גרינגער. וואָס איז אייער נאָמען? [תּלמיד] לוקאַס. רעוויזיע 1. אָוקיי. נידעריק איז וואָס מיר גערופן אָנהייב פריער. אַרויף איז נישט גאַנץ וואָס מיר גערופן סוף פריער. פאקטיש, סוף איז איצט ין די מענגע. עס ס אַן עלעמענט מיר זאָל באַטראַכטן. אַזוי נידעריק איז 0, אַרויף איז די גרייס פון דעם מענגע - 1, און איצט מיר זענען לופּינג, און מיר זענען קאָנטראָלירונג - איך טרעפן איר קענען גיין דורך אים. וואָס איז דיין טראכטן דורך דעם? גיין אונדז דורך דיין קאָד. [תּלמיד] זיכער. קוק בייַ די כייסטאַק ווערט אין דער מיטן און פאַרגלייַכן אים צו נאָדל. אַזוי אויב עס ס גרעסער ווי דיין נאָדל, דעמאָלט איר ווילן צו - אָה, פאקטיש, אַז זאָל זייַן קאַפּויער. איר רע געגאנגען צו וועלן צו וואַרפן אַוועק די רעכט האַלב, און אַזוי יאָ, וואָס זאָל זייַן דער וועג. [באָוודען] אזוי דאָס זאָל זייַן ווייניקער? איז אַז וואָס איר האט? >> [תּלמיד] יאָ. [באָוודען] אָוקיי. ווייניקער. אַזוי אויב וואָס מיר רע קוקן אין איז קלענערער ווי וואָס מיר ווילן, דעמאָלט יאָ, מיר וועלן צו וואַרפן אַוועק די לינקס האַלב, וואָס מיטל מיר זענען אַפּדייטינג אַלץ מיר רע קאָנסידערינג דורך מאָווינג נידעריק צו די רעכט פון די מענגע. דאס קוקט גוט. איך טראַכטן עס האט די זעלבע אַרויסגעבן אַז מיר געזאגט אויף די פֿריִערדיקע איינער, ווו אויב נידעריק איז 0 און זיך איז 1, דעמאָלט נידעריק + אַרויף / 2 איז געגאנגען צו שטעלן אַרויף צו זייַן די זעלבע זאַך ווידער. 

און אַפֿילו אויב אַז ס 'נישט דער פאַל, עס איז נאָך מער עפעקטיוו אין די זייער מינדסטער צו נאָר וואַרפן אַוועק די עלעמענט מיר נאָר געקוקט אין וואָס מיר וויסן איז פאַלש. אַזוי נידעריק + אַרויף / 2 + 1 - >> [תּלמיד] אַז זאָל זייַן די אנדערע וועג. [באָוודען] אָדער דאָס זאָל זייַן - 1 און די אנדערע איינער זאָל זייַן + 1. [תּלמיד] און עס זאָל זייַן אַ טאָפּל יקוואַלז צייכן. >> [באָוודען] יאָ. [תּלמיד] יאָ. אָוקיי. און לעסאָף, איצט אַז מיר האָבן דעם + 1-1 זאַך, איז עס - עס זאל ניט זייַן - איז עס אלץ מעגלעך פֿאַר נידעריק צו סוף אַרויף מיט אַ ווערט גרעסער ווי אַרויף? איך טראַכטן די בלויז וועג וואָס קענען פּאַסירן - איז עס מעגלעך? >> [תּלמיד] איך טאָן ניט וויסן. אבער אויב עס געץ טראַנגקייטיד און דעמאָלט געץ מינוס אַז 1 און דעמאָלט - >> יאָ. [תּלמיד] עס וואָלט עפשער באַקומען מעסט אַרויף. איך טראַכטן עס זאָל זייַן גוט בלויז ווייַל פֿאַר אים צו סוף אַרויף נידעריקער זיי וואָלט האָבן צו זייַן גלייַך, איך טראַכטן. אבער אויב זיי זענען גלייַך, דעמאָלט מיר וואָלט נישט האָבן געטאן די בשעת שלייף צו אָנהייבן מיט און מיר נאָר וואָלט האָבן אומגעקערט דעם ווערט. אַזוי איך טראַכטן מיר רע גוט איצט. נאָטיץ אַז אַפֿילו כאָטש דעם פּראָבלעם איז ניט מער רעקורסיווע, די זעלבע מין פון געדאנקען צולייגן ווו מיר קענען זען ווי דעם אַזוי לייכט לענדז זיך צו אַ רעקורסיווע לייזונג דורך דעם פאַקט אַז מיר רע נאָר אַפּדייטינג די ינדיסעס איבער און איבער ווידער, מיר רע מאכן די פּראָבלעם קלענערער און קלענערער, ​​מיר רע פאָוקיסינג אויף אַ סאַבסעט פון די מענגע. [תּלמיד] אויב נידעריק איז 0 און זיך איז 1, זיי וואָלט ביידע זייַן 0 + 1/2, וואָס וואָלט גיין צו 0, און דעמאָלט איינער וואָלט זייַן + 1, איינער וואָלט זייַן - 1. [תּלמיד] וואו זענען מיר קאָנטראָלירונג יקוואַלאַטי? ווי אויב די מיטל איינער איז פאקטיש נאָדל? מיר רע נישט דערווייַל טאן וואָס? אָה! אויב יץ - יא. מיר קענען ניט נאָר טאָן די פּרובירן אַראָפּ דאָ ווייַל לאָזן ס זאָגן דער ערשטער מיטל - [תּלמיד] עס ס פאקטיש ווי נישט וואַרפן אַוועק די געבונדן. אַזוי אויב איר וואַרפן אַוועק די געבונדן, איר האָבן צו טשעק עס ערשטער אָדער וועלכער. אַ. יאָ. >> [תּלמיד] יאָ. אַזוי איצט מיר האָבן ארלנגעווארפן אַוועק דער איינער מיר דערווייַל געקוקט בייַ, וואָס מיטל מיר איצט דאַרפֿן צו אויך האָבן אויב (כייסטאַק [(נידעריק + אַרויף) / 2] == נאָדל), דעמאָלט מיר קענען צוריקקומען אמת. און צי איך שטעלן אַנדערש אָדער נאָר אויב, עס מיטל ממש די זעלבע זאַך ווייַל דאָס וואָלט האָבן אומגעקערט אמת. אַזוי איך וועט שטעלן אַנדערש אויב, אָבער עס טוט נישט ענין. 

אַזוי אַנדערש אויב דעם, אַנדערש דעם, און דאָס איז אַ פּראָסט זאַך איך טאָן ווו אַפֿילו אויב עס איז דער פאַל ווו אַלץ איז גוט דאָ, ווי נידעריק קענען קיינמאָל זייַן גרעסער ווי אַרויף, עס ס 'נישט ווערט ריזאַנינג וועגן צי אַז ס' אמת. אַזוי איר זאלט ​​ווי געזונט זאָגן בשעת נידעריק איז ווייניקער ווי אָדער גלייַך צו אָדער בשעת נידעריק איז ווייניקער ווי אַזוי אויב זיי זענען אלץ גלייַך אָדער נידעריק כאַפּאַנז צו פאָרן אַרויף, דעמאָלט מיר קענען ברעכן אויס פון דעם שלייף. שאלות, קאַנסערנז, באַמערקונגען? אָוקיי. דאס קוקט גוט. איצט מיר ווילן צו טאָן סאָרט. אויב מיר גיין צו מיין רגע רעוויזיע, מיר זען די זעלבע נומערן, אָבער איצט זיי זענען ניט מער אין אויסגעשטעלט סדר. און מיר ווילן צו מאַכשער סאָרט ניצן קיין אַלגערידאַם אין אָ פון N קלאָץ ען. אַזוי וואָס אַלגערידאַם טאָן איר טראַכטן מיר זאָל מאַכשער דאָ? >> [תּלמיד] מערדזש סאָרט. [באָוודען] יאָ. צונויפגיסן סאָרט איז אָ (N קלאָץ N), אַזוי אַז ס וואָס מיר רע געגאנגען צו טאָן. און דער פּראָבלעם איז געגאנגען צו זייַן שיין ענלעך, ווו עס לייכט לענדז זיך צו אַ רעקורסיווע לייזונג. מיר קענען אויך קומען אַרויף מיט אַ יטערייטיוו לייזונג אויב מיר ווילן, אָבער רעקורסיאָן וועט זייַן גרינגער דאָ און מיר זאָל טאָן רעקורסיאָן. איך טרעפן מיר וועלן גיין דורך צונויפגיסן סאָרט ערשטער, כאָטש עס איז אַ שיינע ווידעא אויף צונויפגיסן סאָרט שוין. [געלעכטער] אַזוי צונויפגיסן סאָרט עס זענען - איך בין ווייסטינג אַזוי פיל פון דעם פּאַפּיר. אָה, דאָרט ס נאָר איין לינקס. אַזוי צונויפגיסן. אָה, 1, 3, 5. אָוקיי. צונויפגיסן נעמט צוויי באַזונדער ערייז. ינדיווידזשואַלי יענע צוויי ערייז זענען ביידע אויסגעשטעלט. אַזוי דעם מענגע, 1, 3, 5, אויסגעשטעלט. דאס מענגע, 0, 2, 4, אויסגעשטעלט. איצט וואָס צונויפגיסן זאָל טאָן איז פאַרבינדן זיי אין אַ איין מענגע וואָס איז זיך אויסגעשטעלט. אַזוי מיר ווילן אַ מענגע פון ​​נומער 6 וואָס איז געגאנגען צו האָבן די יסודות ין פון עס אין אויסגעשטעלט סדר. 

און אַזוי מיר קענען נעמען מייַלע פון ​​די פאַקט אַז די צוויי ערייז זענען אויסגעשטעלט צו טאָן דאָס אין לינעאַר צייַט, לינעאַר צייַט טייַטש אויב דאָס מענגע איז גרייס X און דאָס איז גרייס י, דעריבער די גאַנץ אַלגערידאַם זאָל זייַן אָ (X + י). אָוקיי. אַזוי פֿירלייגן. [תּלמיד] קען מיר אָנהייב פון די לינקס? אַזוי איר וועט שטעלן דעם 0 אַראָפּ ערשטער און דעריבער די 1 און דעריבער דאָ איר ניטאָ בייַ די 2. אַזוי עס ס מין פון ווי איר האָבן אַ קוויטל אַז ס מאָווינג צו די רעכט. >> [באָוודען] יאָ. פֿאַר ביידע פון ​​די ערייז אויב מיר נאָר פאָקוס אויף די לעפטמאָסט עלעמענט. ווייַל ביידע ערייז זענען אויסגעשטעלט, מיר וויסן אַז די 2 עלעמענטן זענען די קלענסטער יסודות אין אָדער מענגע. אַזוי אַז מיטל אַז 1 פון יענע 2 יסודות מוזן זייַן דער קלענסטער עלעמענט אין אונדזער מערדזשד מענגע. עס פּונקט אַזוי כאַפּאַנז אַז דער קלענסטער איז די מען אויף די רעכט דאָס מאָל. אַזוי מיר נעמען 0, אַרייַנלייגן עס אויף די לינקס ווייַל 0 איז ווייניקער ווי 1, אַזוי נעמען 0, אַרייַנלייגן עס אין אונדזער ערשטער שטעלע, און דאַן מיר דערהייַנטיקן דעם צו איצט פאָקוס אויף דער ערשטער עלעמענט. און איצט מיר איבערחזרן. אַזוי איצט מיר פאַרגלייַכן 2 און 1. 1 איז קלענערער, ​​אַזוי מיר וועט אַרייַנלייגן 1. מיר דערהייַנטיקן דעם טייַטל צו פונט צו דעם באָכער. איצט מיר טאָן עס ווידער, אַזוי 2. דאס וועט דערהייַנטיקן, פאַרגלייַכן די 2, 3. דאס דערהייַנטיקונגען, דעמאָלט 4 און 5. אַזוי וואָס איז צונויפגיסן. 

עס זאָל זייַן שיין קלאָר ווי דער טאָג אַז עס איז לינעאַר צייַט זינט מיר נאָר גיין אַריבער יעדער עלעמענט אַמאָל. און וואָס איז די ביגאַסט שריט צו ימפּלאַמענינג צונויפגיסן סאָרט איז טאן דעם. און עס ס נישט אַז שווער. א פּאָר זאכן צו זאָרג וועגן איז לאָזן ס זאָגן מיר זענען מערדזשינג 1, 2, 3, 4, 5, 6. אין דעם פאַל מיר סוף אַרויף אין דער סצענאַר ווו דאָס איינער איז געגאנגען צו זייַן קלענערער, דעמאָלט מיר דערהייַנטיקן דעם טייַטל, דאָס איינער איז געגאנגען צו זייַן קלענערער, ​​דערהייַנטיקן דעם, דאָס איינער ס קלענערער, ​​און איצט איר האָבן צו דערקענען ווען איר ווע פאקטיש לויפן אויס פון עלעמענטן צו פאַרגלייַכן מיט. זינט מיר האָבן שוין געניצט דאָס גאנצע מענגע, אַלץ אין דעם מענגע איז איצט פּונקט ינסערטאַד אין דאָ. אַזוי אויב מיר אלץ לויפן אין די פונט ווו איינער פון אונדזער ערייז איז גאָר מערדזשד שוין, דעמאָלט מיר נאָר נעמען אַלע די יסודות פון די אנדערע מענגע און אַרייַנלייגן זיי אין די סוף פון די מענגע. אַזוי מיר קענען נאָר אַרייַנלייגן 4, 5, 6. אָוקיי. וואָס איז איין זאַך צו היטן אויס פֿאַר. ימפּלאַמענינג וואָס זאָל זייַן שריט 1. צונויפגיסן סאָרט דעמאָלט באזירט אויף וואָס, עס ס 2 טריט, 2 נאַריש טריט. זאל ס נאָר געבן דעם מענגע. אַזוי צונויפגיסן סאָרט, שריט 1 איז צו רעקורסיוועלי ברעכן די מענגע אין כאַווז. אַזוי שפּאַלטן דעם מענגע אין כאַווז. מיר איצט האָבן 4, 15, 16, 50 און 8, 23, 42, 108. און איצט מיר טאָן עס ווידער און מיר שפּאַלטן די אין כאַווז. איך וועט נאָר טאָן עס אויף דעם זייַט. אַזוי 4, 15 און 16, 50. מיר וואָלט טאָן די זעלבע זאַך איבער דאָ. און איצט מיר שפּאַלטן עס אין כאַווז ווידער. און מיר האָבן 4, 15, 16, 50. אַזוי וואָס איז אונדזער באַזע פאַל. אַמאָל די ערייז זענען פון נומער 1, דעמאָלט מיר האַלטן מיט די ספּליטינג אין כאַווז. 

איצט וואָס טאָן מיר טאָן מיט דעם? מיר סוף אַרויף דעם וועט אויך ברעכן אַראָפּ אין 8, 23, 42, און 108. אַזוי איצט אַז מיר ניטאָ בייַ דעם פונט, איצט שריט צוויי פון צונויפגיסן סאָרט איז נאָר מערדזשינג פּערז צו די רשימות. אַזוי מיר ווילן צו צונויפגיסן די. מיר נאָר רופן צונויפגיסן. מיר וויסן צונויפגיסן וועט צוריקקומען די אין אויסגעשטעלט סדר. 4, 15. איצט מיר ווילן צו צונויפגיסן די, און אַז וועט צוריקקומען אַ רשימה מיט יענע אין אויסגעשטעלט סדר, 16, 50. מיר צונויפגיסן יענע - איך קען נישט שרייַבן - 8, 23 און 42, 108. אַזוי מיר האָבן מערדזשד פּערז אַמאָל. איצט מיר נאָר צונויפגיסן ווידער. נאָטיץ אַז יעדער פון די רשימות איז אויסגעשטעלט אין זיך, און דעמאָלט מיר קענען נאָר צונויפגיסן די רשימות צו באַקומען אַ רשימה פון נומער 4 וואָס איז אויסגעשטעלט און צונויפגיסן די צוויי רשימות צו באַקומען אַ רשימה פון נומער 4 וואָס איז אויסגעשטעלט. און לעסאָף, מיר קענען צונויפגיסן יענע צוויי רשימות פון נומער 4 צו באַקומען איין רשימה פון נומער 8, וואס איז אויסגעשטעלט. אַזוי צו זען אַז דאָס איז קוילעלדיק N קלאָץ N, מיר שוין געזען אַז צונויפגיסן איז לינעאַר, אַזוי ווען מיר רע דילינג מיט מערדזשינג די, אַזוי ווי די קוילעלדיק פּרייַז פון צונויפגיסן פֿאַר די צוויי רשימות איז נאָר 2 ווייַל - אָדער געזונט, עס ס אָ פון N, אָבער N דאָ איז נאָר די 2 יסודות, אַזוי עס ס 2. און די 2 וועט זייַן 2 און די 2 וועט זייַן 2 און די 2 וועט זייַן 2, אַזוי אַריבער אַלע פון ​​די מערדזשיז אַז מיר דאַרפֿן צו טאָן, מיר סוף אַרויף טאן ען. ווי 2 + 2 + 2 + 2 איז 8, וואָס איז N, אַזוי די פּרייַז פון מערדזשינג אין דעם גאַנג איז ען. און דעריבער די זעלבע זאַך דאָ. מיר וועט צונויפגיסן די 2, דעריבער די 2, און ינדיווידזשואַלי דעם צונויפגיסן וועלן נעמען פיר אַפּעריישאַנז, דעם צונויפגיסן וועלן נעמען פיר אַפּעריישאַנז, אָבער אַמאָל ווידער, צווישן אַלע פון ​​די, מיר סוף אַרויף מערדזשינג N גאַנץ זאכן, און אַזוי דעם שריט נעמט ען. און אַזוי יעדער מדרגה נעמט N יסודות זייַענדיק מערדזשד. 

און ווי פילע לעוועלס זענען דאָרט? אין יעדער מדרגה, אונדזער מענגע וואקסט דורך נומער 2. דאָ אונדזער ערייז זענען פון נומער 1, דאָ זיי רע פון ​​נומער 2, דאָ זיי רע פון ​​נומער 4, און לעסאָף, זיי רע פון ​​גרייס 8. אַזוי זינט עס איז דאַבלינג, עס זענען געגאנגען צו זייַן אַ גאַנץ פון קלאָץ N פון די לעוועלס. אַזוי מיט קלאָץ N לעוועלס, יעדער יחיד מדרגה גענומען N גאַנץ אַפּעריישאַנז, מיר באַקומען אַן N קלאָץ N אַלגערידאַם. שאלות? האָט מען שוין געמאכט פּראָגרעס אויף ווי צו מאַכשער דעם? איז ווער עס יז שוין אין אַ שטאַט ווו איך קענען נאָר ציען אַרויף זייער קאָד? איך קענען געבן אַ מינוט. דאס איינער איז געגאנגען צו זייַן מער. איך העכסט רעקאָמענדירן ריקער - איר טאָן ניט האָבן צו טאָן רעקורסיאָן פֿאַר צונויפגיסן ווייַל צו טאָן רעקורסיאָן פֿאַר צונויפגיסן, איר ניטאָ געגאנגען צו האָבן צו פאָרן אַ בינטל פון פאַרשידענע סיזעס. איר קענען, אָבער עס ס אַנויינג. אבער רעקורסיאָן פֿאַר סאָרט זיך איז שיין גרינג. איר נאָר ממש רופן סאָרט אויף לינקס האַלב, סאָרט אויף רעכט האַלב. אָוקיי. ווער עס יז האָבן עפּעס איך קענען ציען אַרויף נאָך? אָדער אַנדערש איך וועט געבן אַ מינוט. אָוקיי. ווער עס יז האָבן עפּעס מיר קענען אַרבעטן מיט? אָדער אַנדערש מיר וועט נאָר אַרבעטן מיט דעם און דעמאָלט יקספּאַנד פון דאָרט. 

ווער עס יז האָבן מער ווי דאָס וואָס איך קענען ציען אַרויף? [תּלמיד] יאָ. איר קענען ציען אַרויף מייַן. >> אַלע רעכט. יא! [תּלמיד] עס זענען געווען אַ פּלאַץ פון באדינגונגען. >> טאַקע, דרייען. קענען איר - [תּלמיד] איך האָבן צו ראַטעווען עס. >> יאָ. אַזוי מיר האבן טאָן די צונויפגיסן סעפּעראַטלי. טאַקע, אָבער עס ס נישט אַז שלעכט. אָוקיי. אַזוי סאָרט איז זיך נאָר פאַך מערגעסאָרטהעלפּ. דערקלערן צו אונדז וואָס מערגעסאָרטהעלפּ טוט. [תּלמיד] מערגעסאָרטהעלפּ שיין פיל טוט די צוויי הויפּט טריט, וואָס איז צו סאָרט יעדער העלפט פון די מענגע און דעריבער צו צונויפגיסן ביידע פון ​​זיי. [באָוודען] אָוקיי, אַזוי געבן מיר אַ רגע. איך טראַכטן דעם - >> [תּלמיד] איך דאַרפֿן צו - יאָ. איך בין פעלנדיק עפּעס. אין צונויפגיסן, איך פאַרשטיין אַז איך דאַרפֿן צו שאַפֿן אַ נייַ מענגע ווייַל איך קען נישט טאָן עס אין פּלאַץ. >> יא. איר קענען נישט. ריכטיק. [תּלמיד] אזוי איך שאַפֿן אַ נייע מענגע. איך Forgot אין די סוף פון צונויפגיסן צו שייַעך-טוישן. אָוקיי. מיר דאַרפֿן אַ נייַ מענגע. אין צונויפגיסן סאָרט, דאָס איז כּמעט שטענדיק אמת. טייל פון די פּרייַז פון אַ בעסער אַלגערידאַם צייַט-קלוג איז כּמעט שטענדיק נידינג צו נוצן אַ ביסל מער זכּרון. אַזוי דאָ, קיין ענין ווי איר טאָן צונויפגיסן סאָרט, איר וואָלט ינעוואַטאַבלי דאַרפֿן צו נוצן עטלעכע עקסטרע זכּרון. ער אָדער זי באשאפן אַ נייַ מענגע. און דאַן איר זאָגן בייַ די סוף מיר נאָר דאַרפֿן צו קאָפּיע נייַ מענגע אין דער אָריגינעל מענגע. [תּלמיד] איך טראַכטן אַזוי, יאָ. איך טאָן ניט וויסן אויב וואָס אַרבעט אין טערמינען פון קאַונטינג דורך דערמאָנען אָדער וועלכער - יאָ, עס וועט אַרבעטן. >> [תּלמיד] אָוקיי. האט איר פּרובירן פליסנדיק דעם? >> [תּלמיד] ניין, נישט נאָך. >> אָוקיי. פּרובירן פליסנדיק עס, און דעמאָלט איך וועט רעדן וועגן אים פֿאַר אַ רגע. [תּלמיד] איך דאַרפֿן צו האָבן אַלע די פֿונקציע פּראָוטאַטייפּס און אַלץ, כאָטש, רעכט? די פֿונקציע פּראָוטאַטייפּס. אָה, איר מיינען ווי - יא. סאָרט איז פאַך מערגעסאָרטהעלפּ. 

אַזוי אין סדר פֿאַר סאָרט צו רופן מערגעסאָרטהעלפּ, מערגעסאָרטהעלפּ מוזן אָדער האָבן שוין דיפיינד איידער סאָרט אָדער מיר נאָר דאַרפֿן די פּראָוטאַטייפּ. נאָר נאָכמאַכן און פּאַפּ אַז. און סימילאַרלי, מערגעסאָרטהעלפּ איז פאַך צונויפגיסן, אָבער צונויפגיסן האט נישט געווען דיפיינד נאָך, אַזוי מיר קענען נאָר לאָזן מערגעסאָרטהעלפּ וויסן אַז וואָס ס וואָס צונויפגיסן איז געגאנגען צו קוקן ווי, און אַז ס וואָס. אַזוי מערגעסאָרטהעלפּ. מיר האָבן אַן אַרויסגעבן דאָ ווו מיר האָבן קיין באַזע פאַל. מערגעסאָרטהעלפּ איז רעקורסיווע, אַזוי קיין רעקורסיווע פֿונקציע איז געגאנגען צו דאַרפֿן עטלעכע סאָרט פון באַזע פאַל צו וויסן ווען צו האַלטן רעקורסיוועלי פאַך זיך. וואָס איז אונדזער באַזע פאַל געגאנגען צו זייַן דאָ? יאָ. [תּלמיד] אויב דער נומער איז 1? >> [באָוודען] יא. אַזוי ווי מיר געזען רעכט דאָרט, מיר פארשטאפט ספּליטינג ערייז אַמאָל מיר גאַט אין ערייז פון נומער 1, וואָס ינעוואַטאַבלי זענען אויסגעשטעלט זיך. אַזוי אויב גרייס יקוואַלז 1, מיר וויסן די מענגע איז שוין אויסגעשטעלט, אַזוי מיר קענען נאָר צוריקקומען. 

נאָטיץ, אז ס פּאָסל, אַזוי מיר טאָן ניט צוריקקומען עפּעס באַזונדער, מיר נאָר צוריקקומען. אָוקיי. אַזוי אַז ס אונדזער באַזע פאַל. איך טרעפן אונדזער באַזע פאַל קען אויך זייַן אויב מיר פּאַסירן צו זייַן מערדזשינג אַ מענגע פון ​​גרייס 0, מיר מיסטאָמע ווילן צו האַלטן בייַ עטלעכע פונט, אַזוי מיר קענען נאָר זאָגן גרייס ווייניקער ווי 2 אָדער ווייניקער ווי אָדער גלייַך צו 1 אַזוי אַז דאָס וועט אַרבעטן פֿאַר קיין מענגע איצט. אָוקיי. אַזוי אַז ס אונדזער באַזע פאַל. איצט טאָן איר ווילן צו גיין אונדז דורך צונויפגיסן? וואָס טאָן אַלע די קאַסעס מיינען? אַרויף דאָ, מיר רע נאָר טאן די זעלבע געדאַנק, דער - [תּלמיד] איך דאַרפֿן צו זייַן גייט פארביי גרייס מיט אַלע די מערגעסאָרטהעלפּ רופט. איך צוגעגעבן גרייס ווי אַ נאָך ערשטיק און עס ס נישט דאָרט, ווי גרייס / 2. [באָוודען] אָה, גרייס / 2, גרייס / 2. >> [תּלמיד] יאָ, און אויך אין די אויבן פונקציאָנירן ווי געזונט. [באָוודען] דאָ? >> [תּלמיד] פונקט גרייס. >> [באָוודען] טאַקע. גרייס, גרייס? >> [תּלמיד] יאָ. [באָוודען] אָוקיי. זאל מיר טראַכטן פֿאַר אַ רגע. צי מיר לויפן אין אַן אַרויסגעבן? מיר רע שטענדיק טרעאַטינג די לינקס ווי 0. >> [תּלמיד] נומ אַז ס אומרעכט אויך. אנטשולדיגט. עס זאָל זייַן אָנהייב. יאָ. [באָוודען] אָוקיי. איך ווי אַז בעסער. און סוף. אָוקיי. אַזוי איצט טאָן איר ווילן צו גיין אונדז דורך צונויפגיסן? >> [תּלמיד] אָוקיי. איך בין נאָר גיין דורך דעם נייַ מענגע אַז איך ווע באשאפן. זייַן גרייס איז די גרייס פון דעם חלק פון די מענגע אַז מיר ווילן צו זייַן אויסגעשטעלט און טריינג צו געפֿינען די עלעמענט אַז איך זאָל שטעלן אין די נייַ מענגע שריט. אַזוי צו טאָן וואָס, קודם איך בין קאָנטראָלירונג אויב די לינקס האַלב פון די מענגע האלט צו האָבן קיין מער יסודות, און אויב עס טוט נישט, דעמאָלט איר גיין אַראָפּ צו אַז אַנדערש צושטאַנד, וואָס נאָר זאגט אָוקיי, עס מוזן זייַן אין די רעכט מענגע, און מיר וועט שטעלן אַז אין די קראַנט אינדעקס פון נעוואַררייַ. 

און דעריבער אַנדערש, איך בין קאָנטראָלירונג אויב די רעכט זייַט פון די מענגע איז אויך פאַרטיק, אין וואָס פאַל איך נאָר שטעלן אין די לינקס. וואָס זאל ניט פאקטיש זייַן נייטיק. איך בין נישט זיכער. אבער סייַ ווי סייַ, די אנדערע צוויי טשעק וואָס פון די צוויי זענען קלענערער אין די לינקס אָדער די רעכט. און אויך אין יעדער פאַל, איך בין ינקרעמענטינג וועלכער פּלאַסעהאָלדער איך ינקראַמאַנט. [באָוודען] אָוקיי. וואָס קוקט גוט. טוט ווער עס יז האָבן באַמערקונגען אָדער קאַנסערנז אָדער שאלות? אַזוי די פיר פאלן וואָס מיר האָבן צו ברענגען דאס אין נאָר זייַענדיק - אָדער עס קוקט ווי פינף - אָבער מיר האָבן צו באַטראַכטן צי די לינקס מענגע האט לויפן אויס פון זאכן מיר דאַרפֿן צו צונויפגיסן, צי די רעכט מענגע האט לויפן אויס פון זאכן מיר דאַרפֿן צו צונויפגיסן - איך בין פּוינטינג בייַ גאָרנישט. אַזוי צי די לינקס מענגע האט לויפן אויס פון זאכן אָדער די רעכט מענגע האט לויפן אויס פון זאכן. יענע זענען צוויי פאלן. מיר אויך דאַרפֿן די נישטיק פאַל פון צי די לינקס זאַך איז ווייניקער ווי די רעכט זאַך. דעמאָלט מיר ווילן צו קלייַבן די לינקס זאַך. יענע זענען די קאַסעס. אַזוי דאָס איז רעכט, אַזוי אַז ס וואָס. מענגע לינקס. עס ס 1, 2, 3. אָוקיי. אַזוי יאָ, יענע זענען די פיר זאכן מיר זאל וועלן צו טאָן. און מיר וועט נישט גיין איבער אַ יטערייטיוו לייזונג. איך וואָלט נישט רעקאָמענדירן - צונויפגיסן סאָרט איז אַ בייַשפּיל פון אַ פֿונקציע וואָס איז ביידע נישט עק רעקורסיווע, עס ס 'נישט גרינג צו מאַכן עס עק רעקורסיווע, אָבער אויך עס ס ניט זייער גרינג צו מאַכן עס יטערייטיוו. דאס איז זייער גרינג. דאס ימפּלאַמענטיישאַן פון צונויפגיסן סאָרט, צונויפגיסן, קיין ענין וואָס איר טאָן, איר ניטאָ געגאנגען צו בויען צונויפגיסן. 

אַזוי צונויפגיסן סאָרט געבויט אויף שפּיץ פון צונויפגיסן רעקורסיוועלי איז נאָר די דרייַ שורות. יטעראַטיוועלי, עס איז מער אַנויינג און מער שווער צו טראַכטן וועגן. אבער באַמערקן אַז עס ס נישט עק רעקורסיווע זינט מערגעסאָרטהעלפּ - ווען עס רופט זיך - עס נאָך דאַרף צו טאָן זאכן נאָך דעם רעקורסיווע רופן קערט. אַזוי דעם אָנלייגן ראַם מוזן פאָרזעצן צו עקזיסטירן אַפֿילו נאָך פאַך דעם. און דעריבער ווען איר רופן דעם, די אָנלייגן ראַם מוזן פאָרזעצן צו עקזיסטירן ווייַל אַפֿילו נאָך וואָס רופן, מיר נאָך דאַרפֿן צו צונויפגיסן. און עס איז נאָנטריוויאַל צו מאַכן דעם עק רעקורסיווע. שאלות? אַלע רעכט. אַזוי געגאנגען צוריק צו סאָרט - אָה, דאָרט ס צוויי זאכן איך ווילן צו ווייַזן. אָוקיי. געגאנגען צוריק צו סאָרט, מיר וועט טאָן דעם געשווינד. אָדער זוכן. סאָרט? סאָרט. יאָ. גיי צוריק צו די ביגינינגז פון סאָרט. מיר ווילן צו שאַפֿן אַ אַלגערידאַם אַז סאָרץ די מענגע ניצן קיין אַלגערידאַם אין אָ פון ען. אַזוי ווי איז דאָס מעגלעך? טוט ווער עס יז האָבן קיין סאָרט פון - איך כינטיד איידער בייַ - אויב מיר רע וועגן צו פֿאַרבעסערן פון N קלאָץ N צו אָ פון N, מיר האָבן ימפּרוווד אונדזער אַלגערידאַם צייַט-קלוג, וואָס מיטל וואָס זענען מיר געגאנגען צו דאַרפֿן צו טאָן צו מאַכן אַרויף פֿאַר וואָס? [תּלמיד] ספעיס. >> יאָ. מיר רע געגאנגען צו זייַן ניצן מער פּלאַץ. און ניט אַפֿילו נאָר מער פּלאַץ, עס ס עקספּאָונענשאַלי מער פּלאַץ. אַזוי איך טראַכטן דעם טיפּ פון אַלגערידאַם איז פּסעוודאָ עפּעס, פּסעוודאָ פּאָלינאָם - פּסעוודאָ - איך קען נישט געדענקען. פּסעוודאָ עפּעס. אבער עס ס ווייַל מיר דאַרפֿן צו נוצן אַזוי פיל פּלאַץ אַז דאָס איז אַטשיוואַבאַל אָבער ניט רעאַליסטיש. 

און ווי טאָן מיר דערגרייכן דעם? מיר קענען דערגרייכן דעם אויב מיר גאַראַנטירן אַז קיין באַזונדער עלעמענט אין דער מענגע איז ווייטער אַ זיכער גרייס. אַזוי לאָזן ס נאָר זאָגן אַז נומער איז 200, קיין עלעמענט אין אַ מענגע איז ווייטער נומער 200. און דאָס איז פאקטיש זייער רעאַליסטיש. איר קענען זייער לייכט האָבן אַ מענגע אַז איר וויסן אַלץ אין עס איז געגאנגען צו זייַן ווייניקער ווי עטלעכע נומער. ווי אויב איר האָבן עטלעכע לעגאַמרע מאַסיוו וועקטאָר אָדער עפּעס אָבער איר וויסן אַלץ איז געגאנגען צו זייַן צווישן 0 און 5, דעמאָלט עס ס געגאנגען צו זייַן באטייטיק פאַסטער צו טאָן דעם. און די געבונדן אויף קיין פון די עלעמענטן איז 5, אַזוי דעם געבונדן, וואָס איז ווי פיל זכּרון איר ניטאָ געגאנגען צו זייַן ניצן. אַזוי די געבונדן איז 200. אין טעאָריע עס איז שטענדיק אַ געבונדן זינט אַ ינטעגער קענען נאָר זייַן אַרויף צו 4000000000, אָבער אַז ס אַנריליסטיק זינט דעמאָלט מיר 'ד ווערן ניצן אָרט אויף די סדר פון 4000000000. אַזוי אַז ס אַנריליסטיק. אבער דאָ מיר וועט זאָגן אונדזער געבונדן איז 200. די קונץ צו טאן עס אין אָ פון N איז מיר מאַכן אן אנדער מענגע גערופן קאַונץ פון גרייס געבונדן. אַזוי פאקטיש, דאָס איז אַ דורכוועג פֿאַר - איך פאקטיש טאָן ניט וויסן אויב קלאַנג טוט דאָס. אבער אין גקק בייַ די זייער מינדסטער - אַם אַסומינג קלאַנג טוט עס אויך - דאָס וועט נאָר ינישאַלייז די גאנצע מענגע צו זייַן 0ס. אַזוי אויב איך טאָן נישט וועלן צו טאָן וואָס, דעמאָלט איך קען סעפּעראַטלי טאָן פֿאַר (ינט איך = 0; איך <געבונדן; איך + +) און קאַונץ [איך] = 0; אַזוי איצט אַלץ איז ינישאַלייזד צו 0. איך יטעראַטע איבער מיין מענגע, און וואָס איך בין טאן איז איך בין קאַונטינג די נומער פון יעדער - זאל ס גיין אַראָפּ דאָ. מיר האָבן 4, 15, 16, 50, 8, 23, 42, 108. וואָס איך בין קאַונטינג איז די נומער פון פֿאַלן פון יעדער פון יענע עלעמענטן. זאל ס 'פאקטיש לייגן אַ פּאָר מער אין דאָ מיט עטלעכע ריפּיץ. אַזוי דער ווערט מיר האָבן דאָ, די ווערט פון וואָס איז געגאנגען צו זייַן מענגע [איך]. אַזוי וואַל קען זייַן 4 אָדער 8 אָדער וועלכער. און איצט איך בין קאַונטינג ווי פילע פון ​​וואָס ווערט איך ווע געזען, אַזוי קאַונץ [וואַל] + +; נאָך דעם איז געשען, קאַונץ איז געגאנגען צו קוקן עפּעס ווי 0001. זאל ס טאָן קאַונץ [וואַל] - געבונדן + 1. 

איצט אַז ס נאָר צו חשבון פֿאַר דער פאַקט אַז מיר רע סטאַרטינג פון 0. אַזוי אויב 200 איז געגאנגען צו זייַן אונדזער גרעסטן נומער, דעמאָלט 0-200 איז 201 זאכן. אַזוי קאַונץ, עס וועט קוקן ווי 00,001 ווייַל מיר האָבן איין 4. דעמאָלט מיר וועט האָבן 0001 ווו מיר וועט האָבן אַ 1 אין די 8 אינדעקס פון ציילן. מיר וועט האָבן אַ 2 אין די 23 אינדעקס פון ציילן. מיר וועט האָבן אַ 2 אין די 42 אינדעקס פון ציילן. אַזוי מיר קענען נוצן ציילן. אַזוי נומ_אָפ_יטעם = קאַונץ [איך]. און אַזוי אויב נומ_אָפ_יטעם איז 2, אַז מיטל מיר ווילן צו אַרייַנלייגן 2 פון די נומער איך אין אונדזער אויסגעשטעלט מענגע. אַזוי מיר דאַרפֿן צו האַלטן שפּור פון ווי ווייַט מיר זענען אין די מענגע. אַזוי אינדעקס = 0. מענגע - איך וועט נאָר שרייַבן עס. קאַונץ - מענגע [אינדעקס + +] = איך; איז אַז וואָס איך וועלן? איך טראַכטן אַז ס וואָס איך ווילן. יא, דאָס קוקט גוט. אָוקיי. אַזוי טוט אַלעמען פֿאַרשטיין וואָס דער ציל פון מיין קאַונץ מענגע איז? עס איז קאַונטינג די נומער פון פֿאַלן פון יעדער פון די נומערן. דעמאָלט איך בין יטעראַטינג איבער אַז קאַונץ מענגע, און די יטה שטעלע אין דער קאַונץ מענגע איז די נומער פון איך ס וואָס זאָל דערשייַנען אין מיין אויסגעשטעלט מענגע. אַז ס וואָס קאַונץ פון 4 איז געגאנגען צו זייַן 1 און קאַונץ פון 8 איז געגאנגען צו זייַן 1, קאַונץ פון 23 איז געגאנגען צו זייַן 2. אַזוי אַז ס ווי פילע פון ​​זיי איך ווילן צו אַרייַנלייגן אין מיין אויסגעשטעלט מענגע. דעמאָלט איך נאָר טאָן אַז. איך בין ינסערטינג נומ_אָפ_יטעם איך ס אין מיין אויסגעשטעלט מענגע. 

שאלות? און אַזוי ווידער, דאָס איז לינעאַר מאָל זינט מיר זענען נאָר יטעראַטינג איבער דעם אַמאָל, אָבער עס ס אויך לינעאַר אין וואָס דעם נומער כאַפּאַנז צו זייַן, און אַזוי עס שווער דעפּענדס אויף וואָס דיין געבונדן איז. מיט אַ געבונדן פון 200, וואָס ס 'נישט אַז שלעכט. אויב דיין געבונדן איז געגאנגען צו זייַן 10,000, דעמאָלט אַז ס אַ ביסל ערגער, אָבער אויב דיין געבונדן איז געגאנגען צו זייַן 4000000000, אַז ס גאָר אַנריליסטיק און דעם מענגע איז געגאנגען צו האָבן צו זייַן פון גרייס 4000000000, וואָס איז אַנריליסטיק. אַזוי אַז ס וואָס. שאלות? [ינאָדאַבאַל תּלמיד ענטפער] >> אָוקיי. איך איינגעזען איין אנדערע זאַך ווען מיר זענען געגאנגען דורך. איך טראַכטן די פּראָבלעם איז געווען אין לוקאַס ס און מיסטאָמע יעדער איין איינער מיר ווע געזען. איך גאָר פֿאַרגעסן. דער בלויז זאַך איך געוואלט צו באַמערקן אויף איז אַז ווען איר ניטאָ דילינג מיט זאכן ווי ינדיסעס, איר קיינמאָל טאַקע זען דעם ווען איר ניטאָ שרייבן אַ פֿאַר שלייף, אָבער טעקניקלי, ווען איר ניטאָ דילינג מיט די ינדיסעס, איר זאָל שיין פיל שטענדיק האַנדלען מיט אַנסיינד ינטאַדזשערז. די סיבה פֿאַר דעם איז ווען איר ניטאָ דילינג מיט געחתמעט ינטאַדזשערז, אַזוי אויב איר האָט 2 געחתמעט ינטאַדזשערז און איר שטעלן זיי צוזאַמען און זיי סוף אַרויף אויך גרויס, דעריבער איר סוף אַרויף מיט אַ נעגאַטיוו נומער. אַזוי אַז ס וואָס ינטעגער לויפן איז. 

אויב איך לייג 2000000000 און 1000000000, איך סוף אַרויף מיט נעגאַטיוו 1000000000. אַז ס ווי ינטאַדזשערז אַרבעט אויף קאָמפּיוטערס. אַזוי דער פּראָבלעם מיט ניצן - אַז ס פייַן חוץ אויב נידעריק כאַפּאַנז צו זייַן 2000000000 און אַרויף כאַפּאַנז צו זייַן 1000000000, דעמאָלט דעם איז געגאנגען צו זייַן נעגאַטיוו 1000000000 און דעמאָלט מיר רע געגאנגען צו טיילן אַז דורך 2 און סוף אַרויף מיט נעגאַטיוו 500,000,000. אַזוי דאָס איז בלויז אַן אַרויסגעבן אויב איר פּאַסירן צו זייַן שאַרף דורך אַ מענגע פון ביליאַנז פון זאכן. אבער אויב נידעריק + אַרויף כאַפּאַנז צו לויפן, דעמאָלט אַז ס אַ פּראָבלעם. ווי באַלד ווי מיר מאַכן זיי אַנסיינד, דעמאָלט 2000000000 פּלוס 1000000000 איז 3000000000. 3000000000 צעטיילט דורך 2 איז 1500000000. אַזוי ווי באַלד ווי זיי ניטאָ אַנסיינד, אַלץ איז גאנץ. און אַזוי אַז ס אויך אַן אַרויסגעבן ווען איר ניטאָ שרייבן דיין פֿאַר לופּס, און פאקטיש, עס מיסטאָמע טוט עס אויטאָמאַטיש. עס וועט פאקטיש נאָר שרייַען בייַ איר. אַזוי אויב דעם נומער איז אויך גרויס צו זייַן אין נאָר אַ ינטעגער אָבער עס וואָלט פּאַסיק אין אַ אַנסיינד ינטעגער, עס וועט שרייַען בייַ איר, אַזוי אַז ס וואָס איר קיינמאָל טאַקע לויפן אין די אַרויסגעבן. איר קענען זען אַז אַן אינדעקס איז קיינמאָל געגאנגען צו זייַן נעגאַטיוו, און אַזוי ווען איר ניטאָ יטעראַטינג איבער אַ מענגע, איר קענען כּמעט שטענדיק זאָגן אַנסיינד ינט איך, אָבער איר טאָן ניט טאַקע האָבן צו. דאס זענען געגאנגען צו אַרבעטן שיין פיל נאָר ווי געזונט. אָוקיי. [כוויספּערז] וואָס מאָל איז עס? די לעצטע זאַך איך געוואלט צו ווייַזן - און איך וועט נאָר טאָן עס טאַקע שנעל. איר וויסן ווי מיר האָבן # דעפינירן אַזוי מיר קענען # דעפינירן מאַקס ווי 5 אָדער עפּעס? זאל ס נישט טאָן מאַקס. # דעפינירן געבונדן ווי 200. אַז ס 'וואָס מיר האבן פריער. אַז דיפיינז אַ קעסיידערדיק, וואָס איז נאָר געגאנגען צו זייַן קאַפּיד און פּייסטיד וואוהין מיר פּאַסירן צו שרייַבן געבונדן. 

אַזוי מיר קענען פאקטיש טאָן מער מיט # דיפיינז. מיר קענען # דעפינירן פאַנגקשאַנז. זיי ניטאָ ניט טאַקע פאַנגקשאַנז, אָבער מיר וועט רופן זיי פאַנגקשאַנז. אַ בייַשפּיל וואָלט זייַן עפּעס ווי מאַקס (X, י) איז דיפיינד ווי (X <י? י: X). אָוקיי. אַזוי איר זאָל באַקומען געניצט צו טערנאַרי אָפּעראַטאָר סינטאַקס, אָבער איז X ווייניקער ווי י? צוריקקומען י, אַנדערש צוריקקומען X. אַזוי איר קענען זען איר קענען מאַכן דעם אַ באַזונדער פונקציאָנירן, און די פֿונקציע קען זייַן ווי באָאָל מאַקס נעמט 2 טענות, צוריקקומען דעם. דאס איז איינער פון די מערסט פּראָסט אָנעס איך זען געטאן ווי דעם. מיר רופן זיי מאַקראָס. דאס איז אַ מאַקראָו. דאס איז נאָר די סינטאַקס פֿאַר עס. איר קענען שרייַבן אַ מאַקראָו צו טאָן וועלכער איר ווילן. איר אָפט זען מאַקראָס פֿאַר דיבאַגינג פּרינטפס און שטאָפּן. אַזוי אַ טיפּ פון פּרינטף, עס זענען ספּעציעל קאַנסטאַנץ אין C ווי אַנדערסקאָר ליניע אַנדערסקאָר, 2 שטרייכט ליניע אַנדערסקאָר, און דאָרט ס אויך איך טראַכטן 2 שטרייכט פונק. וואָס זאל זייַן עס. עפּעס ווי אַז. יענע זאכן וועט זייַן ריפּלייסט מיט די נאָמען פון די פֿונקציע אָדער די נומער פון די שורה וואָס איר ניטאָ אויף. אָפט, איר שרייַבן דיבאַגינג פּרינטפס אַז אַראָפּ דאָ איך קען דעריבער נאָר שרייַבן דעבוג און עס וועט דרוקן די שורה נומער און פונקציאָנירן אַז איך פּאַסירן צו זייַן אין אַז עס געפּלאָנטערט אַז דעבוג סטאַטעמענט. און איר קענען אויך דרוקן אנדערע זאכן. אַזוי איין זאַך איר זאָל וואַך אויס פֿאַר איז אויב איך פּאַסירן צו # דעפינירן דאָובלע_מאַקס ווי עפּעס ווי 2 * י און 2 * X. אַזוי פֿאַר וועלכער סיבה, איר פּאַסירן צו טאָן אַז אַ פּלאַץ. אַזוי מאַכן עס אַ מאַקראָו. דאס איז פאקטיש צעבראכן. איך וואָלט רופן עס דורך טאן עפּעס ווי דאָובלע_מאַקס (3, 6). אַזוי וואָס זאָל זייַן אומגעקערט? [תּלמיד] 12. יא, 12 זאָל זייַן אומגעקערט, און 12 איז אומגעקערט. 3 געץ ריפּלייסט פֿאַר X, 6 געץ ריפּלייסט פֿאַר י, און מיר צוריקקומען 2 * 6, וואָס איז 12. איצט וואָס וועגן דעם? וואָס זאָל זייַן אומגעקערט? [תּלמיד] 14. >> ידעאַללי, 14. די אַרויסגעבן איז אַז ווי האַש דיפיינז אַרבעט, געדענקען עס ס אַ פּשאַט - פּאָשעט קאָפּיע און פּאַפּ פון שיין פיל אַלץ, אַזוי וואָס דאָס איז געגאנגען צו זייַן ינטערפּראַטאַד ווי איז 3 ווייניקער ווי 1 פּלוס 6, 2 מאל 1 פּלוס 6, 2 מאל 3. 

אַזוי פֿאַר דעם סיבה איר כּמעט שטענדיק ייַנוויקלען אַלץ אין קלאַמערן. קיין בייַטעוודיק איר כּמעט שטענדיק ייַנוויקלען אין קלאַמערן. עס זענען פאלן ווו איר טאָן ניט האָבן צו, ווי איך וויסן אַז איך טאָן ניט דאַרפֿן צו טאָן אַז דאָ ווייַל ווייניקער ווי איז שיין פיל שטענדיק נאָר געגאנגען צו אַרבעטן, כאָטש וואָס זאל נישט אַפֿילו זייַן אמת. אויב עס איז עפּעס לעכערלעך ווי דאָובלע_מאַקס (1 == 2), דעמאָלט אַז ס געגאנגען צו באַקומען ריפּלייסט מיט 3 ווייניקער ווי 1 יקוואַלז יקוואַלז 2, און אַזוי דעמאָלט עס ס געגאנגען צו טאָן 3 ווייניקער ווי 1, טוט וואָס גלייַך 2, וואָס איז נישט וואָס מיר ווילן. אַזוי אין סדר צו פאַרמייַדן קיין אָפּעראַטאָר פאָרהאַנט פּראָבלעמס, שטענדיק ייַנוויקלען אין קלאַמערן. אָוקיי. און אַז ס עס, 5:30. אויב איר האָט קיין שאלות אויף די פּסעט, לאָזן אונדז וויסן. עס זאָל זייַן שפּאַס, און די העקער Edition אויך איז פיל מער רעאַליסטיש ווי די העקער אויסגאבע פון ​​לעצטע יאָר ס, אַזוי מיר האָפֿן אַז אַ פּלאַץ פון איר פּרובירן עס. לעצטע יאָר ס 'איז געווען זייער אָוווערוועלמינג. 

[CS50.TV]