>> [عزف الموسيقى]
>> أستاذ: حسنا.
هذا هو CS50 وهذا هو نهاية الأسبوع الثلاثة.
لذلك نحن هنا اليوم، وليس في ساندرز المسرح، بدلا من ذلك في مكتبة فايدنر.
داخل وهو الاستوديو المعروفة باسم هاوزر ستوديو،
أو نقول ستوديو H، أو بما يلي نحن say-- إذا كنت تتمتع تلك النكتة،
انها في الواقع من زميل، مارك، على شبكة الإنترنت،
الذي اقترح بقدر عبر تويتر.
الآن ما هو بارد حول ويجري هنا في الاستوديو
وأنني محاط هذه الأخضر الجدران، شاشة خضراء أو chromakey،
إذا جاز التعبير، وهو ما يعني أن لCS50 فريق الإنتاج، دون علم مني
الآن، يمكن أن يكون وضع لي أكثر في أي مكان في العالم،
للأفضل أو للأسوأ.
>> الآن ما ينتظرنا في المستقبل، مشكلة مجموعة اثنين في يديك لهذا الأسبوع،
ولكن مع مشكلة تعيين ثلاثة في الأسبوع المقبل،
سوف تحدى مع ما يسمى عبة 15،
لصالح الحزب القديم الذي تذكرون تلقي
كطفل لديه مجموعة كاملة من الأرقام التي يمكن أن تنزلق إلى أعلى أو أسفل،
اليسار واليمين، وهناك فجوة واحدة ضمن اللغز، الذي قمت
في الواقع يمكن أن تنزلق تلك القطع اللغز.
في نهاية المطاف ظهور هذه لغز في بعض الأمر شبه عشوائي،
والهدف من ذلك هو ترتيب هذا الامر، أعلى إلى أسفل،
من اليسار إلى اليمين، من واحدة كل وسيلة تصل إلى 15.
>> للأسف، وتنفيذ سيكون لديك في متناول اليد
سيكون البرنامج مقرها، وليس جسديا.
وأنت تسير في الواقع لدينا لإرسال كود الذي طالب أو يمكن للمستخدم
تلعب لعبة 15.
في واقع الأمر، في هاكر طبعة من لعبة ال 15،
عليك أن تكون تحديا لتنفيذ، وليس فقط اللعب في هذه المدرسة القديمة
اللعبة، ولكن بدلا من حل من ذلك، تنفيذ وضع الله،
إذا جاز التعبير، وهذا في الواقع يحل اللغز للإنسان،
من خلال تزويدهم التلميح، بعد التلميح، بعد تلميح.
أكثر من ذلك على ان الاسبوع المقبل.
ولكن هذا ما ينتظرنا في المستقبل.
>> في الوقت الراهن أذكر أنه في وقت سابق هذا الاسبوع كان لدينا هذا التشويق، اذا صح التعبير،
حيث أفضل ما كانوا يفعلون الفرز كان من الحكمة الحد الأعلى من كبير س ن
المربعة.
وبعبارة أخرى، فقاعة النوع، نوع الاختيار، والإدراج النوع،
كل منهم، في حين مختلفة في تنفيذها،
تؤول إلى ن مربع تشغيل الوقت في أسوأ جدا القضية.
ونحن نفترض عموما أن أسوأ جدا حالة لفرز
واحد هو أن المدخلات الخاصة بك هي الوراء تماما.
وبالفعل، اتخذ خطوات قليلة جدا لتنفيذ كل تلك الخوارزميات.
>> الآن في النهاية من الدرجة أذكر، قارنا فقاعة الفرز
ضد اختيار نوع ضد الآخر التي كنا نسميها دمج النوع في ذلك الوقت،
وأقترح أن انه أخذ الاستفادة من الدرس من أسبوع
صفر، فرق تسد.
وتحقيق حد ما نوعا من وغاريتمي إدارة الوقت في نهاية المطاف،
بدلا من شيء هذا التربيعية بحتة.
وانها ليست لوغاريتمي جدا، إنها أكثر من ذلك قليلا.
ولكن إذا كنت أذكر من الدرجة، كان من ذلك بكثير، أسرع بكثير.
دعونا نلقي نظرة على النقطة التي توقفنا عندها.
>> فقاعة نوع مقابل اختيار نوع مقابل دمج النوع.
الآن انهم جميعا على التوالي، في نظريا، في نفس الوقت.
هو وحدة المعالجة المركزية تشغيل في نفس السرعة.
ولكن يمكنك أن تشعر كيف مملة هذا وبسرعة جدا سوف تصبح،
ومدى سرعة، ونحن عندما حقن قليلا من خوارزميات الأسبوع الصفر، و
يمكننا تسريع الامور.
>> ذلك النوع علامة تبدو مدهشة.
كيف يمكننا الاستفادة منه، من أجل لفرز الأرقام بسرعة أكبر.
حسنا دعونا نفكر مرة أخرى إلى المقومات التي نحن
كان مرة أخرى في الأسبوع الصفر، وذلك من البحث عن شخص ما في دفتر الهاتف،
وأذكر أن شبة الكود أننا المقترحة،
عبر التي يمكن أن نجد شخص مثل مايك سميث،
بدا شيئا قليلا من هذا القبيل.
>> الآن نلقي نظرة على وجه الخصوص في السطر 7 و 8 و 10 و 11،
الذي حمل هذه الحلقة، حيث حافظنا العودة إلى خط 3 مرة أخرى، ومرة ​​أخرى،
ومره اخرى.
ولكن اتضح أن نتمكن من عرض هذه الخوارزمية، هنا في شبة الكود،
قليلا أكثر شمولية.
في الواقع، ما أنا أبحث في هنا على الشاشة،
هي خوارزمية للبحث عن مايك سميث بين بعض مجموعة من الصفحات.
وبالفعل، فإننا لا يمكن تبسيط هذه الخوارزمية في تلك الخطوط 7 و 8،
و 10 و 11 أن أقول هذا، ولقد قدمت هنا باللون الأصفر.
وبعبارة أخرى، إذا كان مايك سميث في وقت سابق من الكتاب،
نحن لسنا بحاجة لتحديد الخطوة خطوة الآن كيف أن يذهب العثور عليه.
ليس لدينا لتحديد العودة إلى السطر 3،
لماذا لا نحن فقط بدلا من ذلك، مثلا، بشكل عام،
البحث عن مايك في النصف الأيسر من الكتاب.
>> على العكس من ذلك، إذا مايك في الواقع في وقت لاحق في الكتاب،
لماذا لا يمكننا أن أقتبس بحث نهاية الاقتباس لمايك في النصف الأيمن من الكتاب.
وبعبارة أخرى، لماذا لا يمكننا فقط نوع من البونت لأنفسنا قائلين:
البحث عن مايك في هذا فرعية من الكتاب،
وترك الأمر لعملائنا الحاليين خوارزمية ليقول لنا
كيفية البحث عن مايك في أن النصف الأيسر من الكتاب.
وبعبارة أخرى، لدينا الخوارزمية يعمل سواء كان ذلك
دفتر الهاتف من هذا السمك، وهذا سمك، أو أي سمك على الإطلاق.
لذلك يمكننا متكرر تحدد هذه الخوارزمية.
وبعبارة أخرى، على الشاشة هنا، هو خوارزمية
للبحث عن مايك سميث بين صفحات الكتاب الهاتف.
وذلك في السطر 7 و 10، دعنا نقول فقط أن بالضبط.
وأنا استخدم هذا المصطلح لحظة قبل، وبالفعل، العودية
هي الكلمة الطنانة في الوقت الراهن، وانها هذه العملية
القيام بشيء الدورية التي بطريقة أو بأخرى استخدام التعليمات البرمجية التي لديك بالفعل،
واصفا إياه مرة أخرى، ومرة أخرى، ومرة ​​أخرى.
الآن انها سوف تكون مهمة أننا أسفل بطريقة أو بأخرى
بها، ولا تفعل ذلك بلا حدود طويلة.
وإلا فإننا ذاهبون الى لدينا بالفعل حلقة لا نهائية.
ولكن دعونا نرى ما اذا كنا نستطيع استعارة هذه الفكرة من العودية، القيام بشيء جديد
ومرة أخرى، ومرة ​​أخرى، من أجل حل المشكلة الفرز عن طريق دمج
النوع، ومما يزيد من كفاءة.
>> لذلك أنا أعطيك دمج النوع.
لنلقي نظرة.
حتى هنا هو شبة الكود، مع وهو ما يمكن أن تنفذ الفرز،
باستخدام هذه الخوارزمية دعا دمج الفرز.
وانها بكل بساطة هذا.
على إدخال عناصر ن، وبعبارة أخرى، إذا كنت
نظرا ن العناصر والأرقام و خطابات أو أيا كان المدخل هو،
إذا كنت في ضوء العناصر ن، إذا ن أقل من 2، والعودة فقط.
الصحيح؟
لأنه إذا كان n هو أقل من 2، أن يعني أن قائمتي العناصر
اما حجم 0 أو 1، و في كل من هذه الحالات تافهة،
يتم فرز بالفعل القائمة.
إذا لم يكن هناك قائمة، انها فرزها.
وإذا كان هناك قائمة من طول 1، انها مرتبة من الواضح أنه.
لذلك الخوارزمية يحتاج فقط ل حقا شيء مثير للاهتمام،
اذا كان لدينا اثنين أو أكثر العناصر التي أعطيت لنا.
لذلك دعونا ننظر إلى السحر ثم.
آخر فرز النصف الأيسر من العناصر، ثم فرز النصف الأيمن من العناصر،
ثم دمج شطري فرزها.
وما هو نوع من العقل والانحناء هنا، هو أنني لا حقا
ويبدو أن قد قلت لكم أي شيء فقط حتى الآن، أليس كذلك؟
كل ما قلته هو، نظرا لائحة ن العناصر، فرز النصف الأيسر،
ثم النصف الأيمن، ثم دمج شطري فرزها،
ولكن أين هي الخلطة السرية الفعلية؟
أين هو خوارزمية؟
كذلك اتضح أن هذين الخطين أولا، نصف تركت نوعا من العناصر،
والنوع النصف الأيمن من العناصر، هي دعوات متكررة، إذا جاز التعبير.
>> بعد كل شيء، في هذا نقطة في الوقت المناسب، لا بد لي
خوارزمية التي ل فرز مجموعة كاملة من العناصر؟
نعم.
انها هنا.
انها هنا على الشاشة، و حتى أتمكن من استخدام نفس ذلك مجموعة من الخطوات
لفرز النصف الأيسر، ما أستطيع النصف الأيمن.
وبالفعل، مرة أخرى، ومرة ​​أخرى.
لذلك بطريقة أو بأخرى، وسنقوم قريبا نرى هذا، والسحر من دمج النوع
مضمن في المباراة النهائية جدا خط، ودمج شطري فرزها.
والذي يبدو بديهية إلى حد ما.
كنت تأخذ نصفين، ولكم، بطريقة أو بأخرى، دمجها معا،
وسنرى هذا بشكل ملموس في لحظة.
>> ولكن هذا هو خوارزمية كاملة.
ودعونا نرى ماذا بالضبط.
حسنا لنفترض أننا بالنظر إلى هذه نفسها ثمانية عناصر هنا على الشاشة، واحد
من خلال ثمانية، ولكنهم من أجل تبدو عشوائية.
والهدف هو في متناول اليد لفرز هذه العناصر.
حسنا كيف يمكنني التوجه نحو يفعل ذلك باستخدام، مرة أخرى،
دمج النوع، كما في هذا شبة الكود؟
ومرة أخرى، غرس ذلك في عقلك، لمجرد لحظة.
الحالة الأولى هي جميلة تافهة، إذا كان أقل من 2،
العودة فقط، وليس هناك عمل ينبغي القيام به.
ذلك حقا هناك ثلاثة فقط خطوات لإبقاء حقا في الاعتبار.
مرة أخرى، ومرة ​​أخرى، وأنا تريد الذهاب الى ل
لفرز النصف الأيسر، فرز النصف الأيمن،
ثم مرة واحدة على يتم فرز نصفين،
أريد أن دمجها معا في قائمة فرزها واحدة.
حتى أن تبقي في الاعتبار.
>> حتى هنا في القائمة الأصلية.
دعونا نتعامل مع هذا باعتباره مجموعة، كما بدأنا ل
في أسبوعين، وهو كتلة قريبة من الذاكرة.
في هذه الحالة، التي تحتوي على ثمانية أرقام، والعودة إلى العودة إلى الوراء.
ودعونا الآن تطبيق دمج النوع.
لذلك أود أولا أن فرز النصف الأيسر من هذه القائمة،
ودعونا، لذلك، التركيز على 4 و 8 و 6 و 2.
>> الآن كيف أذهب حول فرز قائمة حجم 4؟
حسنا لدي للنظر الآن فرز اليسار في النصف الأيسر.
مرة أخرى، دعونا الترجيع لمجرد لحظة.
إذا كانت شبة الكود هو هذا، وأنا أعطيت ثمانية عناصر،
8 أكبر من الواضح من أو يساوي 2.
حتى مع لا ينطبق على الحالة الأولى.
لذلك لفرز العناصر الثمانية، وأنا أول فرز النصف الأيسر من العناصر،
بعد ذلك فرز النصف الأيمن، ثم يمكنني دمج نصفي فرزها، كل من حجم 4.
حسنا.
>> ولكن إذا كنت قد قال لي فقط، فرز النصف الأيسر، وهو الآن من حجم 4،
كيف يمكنني فرز نصف اليسار؟
حسنا إذا كان لدي المدخلات من أربعة عناصر،
أنا أولا فرز اليسار اثنين، ثم انقر بزر الماوس اثنين،
وبعد ذلك دمجها معا.
ذلك مرة أخرى، فإنه يصبح قليلا من عقل الانحناء لعبة هنا،
لأنك، من نوع، أن أتذكر أين كنت في هذه القصة،
ولكن في نهاية اليوم، يحصل على أي عدد من العناصر،
تريد أولا لفرز النصف الأيسر، ثم النصف الأيمن،
ثم دمجها معا.
دعونا نبدأ لذلك تماما.
وهنا دخل ثمانية عناصر.
الآن نحن نبحث في النصف الأيسر هنا.
كيف يمكنني فرز العناصر الأربعة؟
حسنا أنا أول فرز نصف نقاط.
الآن كيف يمكنني فرز نصف اليسار؟
حسنا لقد أعطيت عنصرين.
لذلك دعونا فرز هذين العنصرين.
2 أكبر من أو تساوي 2، بطبيعة الحال.
لذلك لا تنطبق هذه الحالة الأولى.
>> لذلك ليس لدي الآن لفرز اليسار نصف هذين العنصرين.
النصف الأيسر، بطبيعة الحال، هو فقط 4.
فكيف يمكنني فرز قائمة من عنصر واحد؟
حسنا الآن، هذه الحالة قاعدة خاصة حتى أعلى، إذا جاز التعبير، ينطبق.
1 هو أقل من 2، وبلدي قائمة هو في الواقع من حجم 1.
لذلك أنا فقط العودة.
لا أفعل أي شيء.
والواقع، أن ننظر في ما لدي عمله، 4 يتم فرز بالفعل.
وكأنني بالفعل ناجحة جزئيا هنا.
>> الآن يبدو نوع من الغباء المطالبة، ولكنه صحيح.
4 هي قائمة من حجم 1.
لقد تم فرزها بالفعل.
هذا هو النصف الأيسر.
أنا الآن فرز النصف الأيمن.
بلدي إدخال عنصر واحد، 8 وبالمثل، مرتبة بالفعل.
غبي أيضا، ولكن مرة أخرى، هذا المبدأ الأساسي
سوف تسمح لنا ببناء الآن على رأس هذه بنجاح.
4 فرزها، يتم فرز 8، الآن ما الذي كان الخطوة الأخيرة؟
لذا فإن الخطوة الثالثة والأخيرة، أي الوقت كنت فرز قائمة، أذكر،
كان لدمج شطري، اليسار واليمين.
لذلك دعونا نفعل ذلك بالضبط.
بلدي النصف الأيسر هو، بطبيعة الحال، 4.
بلدي النصف الأيمن هو 8.
>> لذلك دعونا نفعل هذا.
أولا انا ذاهب الى تخصيص بعض ذاكرة إضافية،
التي سوف تمثل هنا، كما مجرد مجموعة الثانوية،
هذا هو كبير بما يكفي لتناسب هذا.
ولكن يمكنك أن تتخيل تمديد هذا المستطيل طول كله،
إذا نحن بحاجة أكثر في وقت لاحق.
كيف يمكنني أخذ 4 و 8، ودمج تلك القائمتين من حجم 1 معا؟
هنا، أيضا، بسيطة جدا.
4 يأتي أولا، ثم يأتي 8.
لأنه إذا أريد لفرز النصف الأيسر، ثم النصف الأيمن،
ثم دمج تلك نصفي معا، من أجل فرزها،
4 يأتي أولا، ثم يأتي 8.
>> لذلك يبدو أننا نحرز تقدما، حتى على الرغم من أنني لم تقم بأي عمل فعلي.
ولكن تذكر ما نحن فيه في القصة.
أخذنا في الأصل ثمانية عناصر.
نحن فرز النصف الأيسر، الذي هو 4.
ثم قمنا بفرز النصف الأيسر من النصف الأيسر، الذي كان 2.
وها قد بدأنا.
نحن القيام به مع هذه الخطوة.
>> حتى إذا قمنا فرز غادر نصف 2، ونحن الآن
يجب أن فرز النصف الأيمن من 2.
حتى النصف الأيمن من 2 هو هذه القيمتين هنا و 6 و 2.
لذلك دعونا الآن أن تتخذ مدخلا من حجم 2، وفرز النصف الأيسر، ومن ثم
النصف الأيمن، ثم دمجها معا.
حسنا كيف يمكنني فرز قائمة من حجم 1، يحتوي فقط على عدد 6؟
انتهيت بالفعل.
يتم فرز تلك القائمة من حجم 1.
>> كيف يمكنني فرز قائمة أخرى من حجم 1، ويسمى النصف الأيمن.
إضافة إلى أنه، أيضا، يتم فرز بالفعل.
عدد 2 وحده.
وحتى الآن لدي نصفين، اليسار و الحق، ولست بحاجة إلى دمجها معا.
اسمحوا لي أن أقدم نفسي بعض مساحة إضافية.
ووضع 2 في هناك، ثم 6 في هناك، وبالتالي
فرز تلك القائمة، اليسار واليمين، ودمجه معا، في نهاية المطاف.
لذلك أنا في وضع أفضل قليلا.
أنا لم تفعل، لأنه من الواضح 4، 8، 2، 6 ليس هو الطلب الأخير الذي أريد.
ولكن لدي الآن قائمتين من حجم 2، أن على حد سواء، على التوالي، تم فرزها.
حتى الآن إذا كنت الترجيع في العقل الخاص بك العين، حيث لم تترك لنا؟
لقد بدأت مع ثمانية عناصر، ثم أنا تتفكك وصولا الى النصف الأيسر من 4
ثم النصف الأيسر من 2، و ثم النصف الأيمن من 2
انتهيت لذلك، والفرز اليسار نصف 2، والنصف الأيمن من 2
فما هي الخطوة الثالثة والأخيرة هنا؟
لا بد لي من دمج معا قائمتين من حجم 2.
لذلك دعونا المضي قدما.
وعلى الشاشة هنا، وإعطاء لي بعض ذاكرة إضافية،
على الرغم من الناحية الفنية، لاحظ أن لدي حصلت على مجموعة كاملة من الفضاء فارغا حتى أعلى
هناك.
إذا كنت تريد أن تكون خاصة الفضاء كفاءة الحكمة،
أنا يمكن أن نبدأ تحريك العناصر ذهابا وإيابا، أعلى وأسفل.
ولكن فقط من أجل الوضوح البصري، انا ذاهب الى وضعها أدناه،
للحفاظ على الأشياء جميلة ونظيفة.
>> حتى لقد حصلت على قائمتين من حجم 2.
القائمة الأولى لديها 4 و 8.
القائمة الثانية بها 2 و 6.
دعونا دمج تلك معا من أجل فرزها.
2، بطبيعة الحال، يأتي أولا، ثم 4 ثم 6 ثم 8.
والآن يبدو أننا الحصول على مثيرة للاهتمام في مكان ما.
نصف الآن لقد تم فرزها من قائمة، وقبيل الصدفة، انها
جميع الأرقام الزوجية، ولكن هذا هو، في الواقع، مجرد صدفة.
وأنا الآن قد فرز اليسار النصف، بحيث انها 2 و 4 و 6 و 8.
لا شيء للخروج من النظام.
وكأننا التقدم.
>> الآن بدا الامر وكأننا لدي كان يتحدث الآن إلى الأبد،
فما يبقى أن نرى ما إذا كان هذا الخوارزمية هي، في الواقع، أكثر كفاءة.
ولكن ونحن في طريقنا من خلال انها عظمى بشكل منهجي.
كمبيوتر، بطبيعة الحال، أن تفعل ذلك من هذا القبيل.
فأين نحن؟
بدأنا مع ثمانية عناصر.
I فرز النصف الأيسر من 4.
يبدو لي أن فعلت مع ذلك.
وحتى الآن فإن الخطوة التالية هي ل فرز النصف الأيمن من 4.
وهذا الجزء يمكننا أن نذهب من خلال قليلا أكثر
بسرعة، على الرغم من أنك كنت مرحبا بكم في الترجيع أو وقفه، فقط
أعتقد من خلال ذلك في وتيرة الخاصة بك، ولكن ماذا
لدينا الآن فرصة ل تفعل نفس خوارزمية الدقيق على أربعة
أرقام مختلفة.
>> لذلك دعونا المضي قدما، والتركيز على النصف الأيمن، والذي نحن هنا.
النصف الأيسر من ذلك النصف الأيمن، والآن
النصف الأيسر من اليسار نصف هذا النصف الأيمن،
وكيف يمكنني فرز قائمة من حجم 1 تحتوي فقط على رقم 1؟
لقد فعلت ذلك.
كيف أفعل نفس الشيء للحصول على قائمة من حجم 1 يحتوي فقط 7؟
لقد فعلت ذلك.
الخطوة الثالثة لهذا الشوط ثم تم دمج هذين العنصرين
في قائمة جديدة من حجم 2، 1 و 7.
لا يبدو أن قد فعلت كل أن هناك الكثير من العمل للاهتمام.
دعونا نرى ما سيحدث بعد ذلك.
أنا فقط فرز النصف الأيسر من النصف الأيمن من بلدي الأصلي المدخل.
الآن دعونا فرز الحق نصف، والذي يحتوي على 5 و 3.
دعونا ننظر مرة أخرى في اليسار نصف وفرزها، النصف الأيمن، مرتبة،
ودمج هذين معا، في بعض مساحة إضافية،
3 يأتي أولا، ثم يأتي 5.
وحتى الآن، لدينا فرز النصف الأيسر من النصف الأيمن
المشكلة الأصلية، و النصف الأيمن من النصف الأيمن
المشكلة الأصلية.
ما هي الخطوة الثالثة والأخيرة؟
حسنا لدمج تلك نصفين اثنين معا.
لذلك اسمحوا لي الحصول على نفسي بعض مساحة إضافية، ولكن، مرة أخرى، وأنا
يمكن أن يكون استخدام هذا الفضاء حتى أعلى الفراغ.
ولكن ونحن في طريقنا للحفاظ على من السهل بصريا.
اسمحوا لي أن دمج في الآن 1، و ثم 3 ثم 5 ثم 7.
ترك لي بذلك الآن مع النصف الأيمن من المشكلة الأصلية
وهذا ما تم فرزها تماما.
>> فما يبقى؟
أشعر وكأنني أقول دائما ل نفس الأشياء مرة أخرى، ومرة ​​أخرى،
ولكن هذا يعكس حقيقة أن نستخدمه العودية.
عملية استخدام الخوارزمية مرة أخرى، ومرة ​​أخرى،
على مجموعات فرعية أصغر من المشكلة الأصلية.
لذلك أنا الآن قد اليسار فرز نصف المشكلة الأصلية.
لدي الصحيح نصف فرزها المشكلة الأصلية.
ما هي الخطوة الثالثة والأخيرة؟
أوه، أنها الدمج.
لذلك دعونا نفعل ذلك.
دعونا تخصيص بعض إضافية الذاكرة، ولكن يا إلهي، نحن
يمكن وضعه في أي مكان الآن.
لدينا الكثير من الفضاء متاحة لنا، ولكننا سوف يبقيه بسيط.
بدلا من الذهاب الى الوراء و إيابا مع الذاكرة الأصلية لدينا،
دعونا فقط تفعل ذلك بصريا إلى هنا أدناه،
إلى الانتهاء من دمج النصف الأيسر والنصف الأيمن.
>> ذلك عن طريق دمج، ماذا يجب أن أفعل؟
وأود أن أغتنم العناصر في النظام.
لذلك يبحث في النصف الأيسر، أرى أن الرقم الأول هو 2.
ألقي نظرة على النصف الأيمن، أرى أن الرقم الأول
هو 1، ومن الواضح أن ذلك الذي عدد تفعل أريد أن أقتلع،
وطرحت لأول مرة في القائمة النهائية بلدي؟
وبطبيعة الحال، 1.
الآن أريد أن أسأل هذا السؤال نفسه.
على النصف الأيسر، لقد لا يزال لديه عدد 2.
على النصف الأيمن، لقد حصلت على عدد 3.
أي واحد لا أريد أن تختار؟
بالطبع، عدد 2 و تلاحظ الآن المرشحين
هي 4 على اليسار و 3 على اليمين.
دعونا، بطبيعة الحال، واختيار 3.
الآن المرشحون هم على 4 اليسار، 5 على اليمين.
ونحن، بالطبع، اختيار 4.
6 على اليسار، 5 على اليمين.
ونحن، بالطبع، اختيار 5.
6 على اليسار، 7 على اليمين.
نختار 6، ومن ثم نحن اختيار 7، ثم نختار 8.
فويلا.
>> لذلك العدد الهائل من الكلمات في وقت لاحق، ونحن وقد فرز هذه القائمة من ثمانية عناصر
في قائمة واحدة خلال ثمانية، هذا ما المتزايد مع كل خطوة،
ولكن كم من الوقت لم يستغرق منا أن نفعل ذلك.
حسنا لقد قمت عمدا الأشياء المبينة بالصور
هنا، لذلك ما في وسعنا نوع من نرى أو نقدر تقسيم
في قهر وهذا ما كان يحدث.
>> في الواقع إذا نظرنا إلى الوراء في أعقاب، لقد تركت كل هذه الخطوط المنقطة
في أصحاب المكان، يمكنك، نوع من، انظر، في ترتيب عكسي،
إذا كنت من النوع ننظر إلى الوراء في التاريخ الآن يا القائمة الأصلية
هو، بطبيعة الحال، من حجم 8.
وبعد ذلك سابقا، كنت التعامل مع قائمتين من حجم 4،
ثم أربع قوائم من حجم 2، ثم ثماني قوائم حجم 1.
>> فماذا يعني هذا، نوع من، أذكركم؟
حسنا، في الواقع، أي من خوارزميات قمنا
نظرت حتى الآن أين نحن الانقسام، والانقسام، والانقسام،
الحفاظ على وجود الأشياء مرة أخرى، و مرة أخرى، يؤدي إلى هذه الفكرة العامة.
وحتى لا يكون هناك شيء وغاريتمي يجري هنا.
وانها ليست السجل تماما من ن، ولكن هناك عنصر لوغاريتمي
ما فعلناه للتو.
>> الآن دعونا النظر في كيفية هذا هو الواقع.
حتى تسجيل ن، ومرة ​​أخرى كان وقت تشغيل العظيم،
عندما فعلنا شيء من هذا القبيل البحث الثنائي، كما نسميها الآن،
استراتيجية فرق تسد عبر التي وجدنا مايك سميث.
الآن من الناحية الفنية.
هذا هو الأساس سجل 2 ن، حتى وإن كان في معظم فصول الرياضيات،
10 عادة القاعدة التي تفترض.
ولكن علماء الكمبيوتر دائما تقريبا التفكير والحديث من حيث قاعدة 2،
لذلك نحن عموما نقول فقط سجل ن، بدلا من قاعدة سجل 2 ن،
ولكنهم واحد بالضبط و نفسه في عالم الكمبيوتر
العلم، وبوصفها جانبا، هناك عاملا ثابتا
الفرق بين الاثنين، لذلك فمن موضع نقاش على أي حال، لأسباب أكثر رسمية.
>> لكنه الآن، ما يهمنا حول هذا المثال.
لذلك دعونا لا يثبت عن طريق القدوة، ولكن في الأقل استخدام مثال على أرقام
في متناول اليد كما شيك التعقل، اذا صح التعبير.
لذلك سابقا كانت صيغة قاعدة السجل 2 ن، ولكن ما هو ن في هذه الحالة.
كان لي الأرقام ن الأصلية، أو 8 من العدد الأصلي على وجه التحديد.
الآن انها كانت قليلا في حين، ولكن أنا جميلة
تأكد أن قاعدة سجل 2 من قيمة 8 هو 3،
وبالفعل، ما هو الجميل في هذا هو أن 3 هو بالضبط عدد المرات
التي يمكنك تقسيم قائمة من طول 8 مرة أخرى، ومرة ​​أخرى،
ومرة أخرى، حتى كنت تركت مع قوائم حجم عادل 1.
الصحيح؟
8 يذهب إلى 4، ويذهب إلى 2، يذهب إلى 1، وهذا هو
يعكس ذلك تماما الصورة كانت لدينا منذ لحظة فقط.
حتى القليل من التعقل تحقق إلى أين اللوغاريتم هو بيت القصيد.
>> وحتى الآن، وماذا تشارك هنا؟ ن.
لذلك نلاحظ أن كل مرة كنت تقسيم القائمة،
وإن كان ذلك في ترتيب عكسي في التاريخ هنا، كنت لا تزال تفعل ن الأشياء.
هذه الخطوة تتطلب أن دمج كنت على اتصال كل واحد من الأرقام،
من أجل أدخلها الموقع المناسب لها.
ذلك على الرغم من ارتفاع هذا الرسم هو من حجم السجل ن ن أو 3،
على وجه التحديد، وبعبارة أخرى، فعلت ثلاثة أقسام هنا.
كيف الكثير من العمل لم أفعل أفقيا إلى جانب هذا المخطط في كل مرة؟
>> حسنا، أنا فعلت ن خطوات العمل، لأنه إذا كان لدي
حصلت أربعة عناصر وأربعة عناصر، ولست بحاجة لدمجها معا.
لست بحاجة للذهاب من خلال هذه الأربعة وهذه الأربعة،
في نهاية المطاف إلى دمجها العودة إلى ثمانية عناصر.
إذا على العكس لقد حصلت على ثمانية أصابع أكثر من هنا، وأنا لا، وثمانية
fingers-- sorry-- إذا كنت قد حصلت أربعة أصابع أكثر من هنا،
الذي أقوم به، وأربعة أصابع أكثر من هنا، والذي أقوم به،
ثم أن نفس الشيء مثلا كما كان من قبل، إذا كنت تفعل
لديها ثمانية أصابع وإن كان في مجموعه، والتي يمكن I، نوع من، القيام به.
يمكنني القيام به بالضبط هنا، ثم يمكنني بالتأكيد
دمج كل هذه القوائم من حجم 1 معا.
ولكن لدي بالتأكيد للنظر في كل عنصر من عناصر مرة واحدة فقط.
وبالتالي فإن ارتفاع هذه العملية هو سجل ن، عرض لهذه العملية، إذا جاز التعبير،
غير ن، فما يبدو أننا أن يكون، في نهاية المطاف، هو
مدته حجم ن مرات تسجيل ن.
>> وبعبارة أخرى، قسمنا القائمة، سجل ن مرات،
لكن في كل مرة فعلنا ذلك، كان لدينا للمس كل واحد من العناصر
من أجل دمجها كل ذلك معا، والتي
وN الخطوة، لذلك لدينا ن مرات تسجيل ن، أو كعالم كمبيوتر أن يقول،
مقارب، التي ستكون كلمة كبيرة
لوصف العلوي ملزمة على إدارة الوقت،
نحن على التوالي في س كبير من سجل ن الوقت، إذا جاز التعبير.
>> الآن هذا أمر مهم، لأن أذكر ما كانت مرات تشغيل
مع فقاعة الفرز، واختيار النوع، والإدراج النوع،
وحتى عدد قليل من الآخرين موجودة، ن مربع وحيث كنا في.
ويمكنك، من نوع، نرى هذا هنا.
إذا كان n تربيع ومن الواضح n مرة ن، ولكن هنا لدينا ن مرات تسجيل ن،
ونحن نعرف بالفعل من أسبوع الصفر، وهذا السجل ن، ووغاريتمي،
أفضل من شيء الخطية.
بعد كل شيء، أذكر الصورة مع الأحمر والأصفر
والخطوط الخضراء التي تعادلنا، و كان الخط الأخضر لوغاريتمي أقل من ذلك بكثير.
وبالتالي، أفضل بكثير وأسرع من الخطوط الصفراء والحمراء على التوالي،
n مرة السجل ن هو، في الواقع، على نحو أفضل من مرات ن ن، ن أو المربعة.
>> لذلك يبدو أننا ل حددت لدمج خوارزمية
النوع الذي يعمل في بكثير أسرع وقت، وبالفعل،
لهذا السبب، في وقت سابق من هذا الأسبوع، عندما رأينا أن المسابقة بين فقاعة
نوع، واختيار نوع، ودمج النوع، ودمج النوع حقا، فاز حقا.
وبالفعل، لم نكن ننتظر حتى لفقاعة فرز واختيار نوع
وحتى النهاية.
>> الآن دعونا نلقي تمريرة الآخر في هذا، من أكثر قليلا
منظور رسمي، فقط في حالة، وهذا صدى أفضل
من ذلك مناقشة مستوى أعلى.
حتى هنا في خوارزمية مرة أخرى.
دعونا نسأل أنفسنا، ما وقت التشغيل
هو من هذه الخوارزميات الخطوات المختلفة؟
دعونا تقسيمه إلى أول حالة والحالة الثانية.
وإذا وآخر في حالة IF، IF n هو أقل من 2، والعودة فقط.
يشعر وكأنه وقت ثابت.
انها، من نوع، مثل خطوتين، IF n هو أقل من 2، ثم العودة.
ولكن كما قلنا يوم الاثنين، وقت ثابت، أو كبيرة س 1،
يمكن أن يكون خطوتين، ثلاثة الخطوات، حتى 1000 الخطوات.
ما يهم هو أنه عدد ثابت من الخطوات.
لذلك سلط الضوء الأصفر شبة الكود هنا يعمل في، ونحن سوف يطلق عليه،
وقت ثابت.
أكثر من ذلك رسميا، و ونحن في طريقنا to-- هذا
سيكون مدى نحن إضفاء الطابع الرسمي على هذا الحق now-- T ن،
إدارة الوقت من مشكلة أن يأخذ ن سمثينغس كمدخل،
يساوي كبيرة يا واحد، IF n هو أقل من 2.
لذلك فمن مشروطا ذلك.
لكي نكون واضحين، إذا كان n أقل من 2، لدينا قائمة قصيرة جدا، ثم
إدارة الوقت، T ن، حيث ن هو 1 أو 0، في هذه الحالة المحددة جدا،
انها مجرد سيكون وقت ثابت.
انها سوف تأخذ واحدة خطوة، خطوتين، أيا كان.
انها عدد محدد من الخطوات.
>> لذلك يجب أن يكون جزءا العصير بالتأكيد في حالة أخرى في pseudocode.
حالة ELSE.
ترتيب النصف الأيسر من العناصر، نوع الحق نصف العناصر، دمج شطري فرزها.
وكم من كل تلك الخطوات تأخذ؟
حسنا، إذا كان تشغيل الوقت لفرز العناصر ن
هو، دعنا نسميها جدا بشكل عام، T ن،
ثم فرز اليسار نصف العناصر
هو، نوع من مثل قوله، T ن مقسوما على 2،
وبالمثل الفرز النصف الأيمن عناصر هي، من نوع، مثل قوله،
T ن تقسيم 2، ومن ثم دمج شطري فرزها.
حسنا إذا كنت قد حصلت على بعض عدد من العناصر هنا،
مثل أربعة، وبعض العدد من العناصر هنا، مثل أربعة،
ولقد لدمج كل من هذه الأربعة في، ولكل من هذه الأربعة في، واحد
بعد الآخر، بحيث في نهاية المطاف لدي ثمانية عناصر.
فهو يبدو وكأنه هذا هو كبير س ن الخطوات؟
إذا كنت قد حصلت على ن الأصابع وكل من منهم لديه المراد دمجها في مكانه،
هذا مثل ن خطوات أخرى.
>> ذلك الواقع formulaically، يمكننا التعبير عن هذا،
وإن كان بالاقتراب قليلا في البداية نظرة، ولكن هو شيء
الذي يلتقط بالضبط هذا المنطق.
إدارة الوقت، T ن، ن IF أكبر من أو تساوي 2.
في هذه الحالة، حالة ELSE، هو T ن مقسوما على 2، بالإضافة إلى T ن مقسوما على 2،
بالإضافة كبير س ن، بعض عدد خطية من الخطوات،
ربما بالضبط ن، ربما 2 مرات ن، لكنه تقريبا، بأمر من ن.
بحيث، أيضا، هو كيف يمكننا التعبير عن هذا formulaically.
الآن أنت لن تعرف هذا إلا إذا كنت قد سجلت في عقلك،
أو البحث عنه في ظهر كتاب، أن
قد يكون قليلا الغش ورقة في النهاية،
ولكن هذا هو، في الواقع، والذهاب إلى تعطينا كبيرة س ن ن السجل،
لأن تكرار ذلك ترونه هنا على الشاشة،
إذا فعلت ذلك فعلا، مع عدد لا حصر له من الأمثلة،
أو يمكنك فعل ذلك formulaically، تفعل نرى أن هذا، لأن هذه الصيغة
في حد ذاته هو العودية، مع طن من ن على شيء على حق،
ور ن الناحية اليسرى، وهذا يمكن في الواقع أن أعرب، في نهاية المطاف،
العودة كبير اعتبارا من ن ن السجل.
إذا لم يقتنع، وهذا غرامة الآن، فقط
تأخذ على الإيمان، أن هذا هو، في الواقع، ما يؤدي ذلك إلى تكرار،
ولكن هذا هو مجرد أكثر قليلا من نهج رياضي لأبحث
في وقت تشغيل دمج النوع بناء على شبة الكود وحدها.
>> الآن دعونا نلقي قليلا من استراحة من كل ذلك،
ونلقي نظرة على بعض السناتور السابق الذي
قد تبدو مألوفة قليلا، الذين جلست مع اريك جوجل
شميت، منذ بعض الوقت، لإجراء مقابلة على خشبة المسرح، أمام مجموعة كاملة
من الناس، والحديث في نهاية المطاف عن موضوع، وهذا الآن جدا مألوفة.
لنلقي نظرة.
>> إريك شميدت: الآن عضو مجلس الشيوخ، كنت هنا في جوجل
وأود أن نفكر في الرئاسة كما مقابلة عمل.
الآن انه من الصعب الحصول على وظيفة رئيسا للبلاد.
الرئيس أوباما: الحق.
إريك شميدت: وكنت تنوي القيام به (غير مسموع) الآن.
كما انها من الصعب الحصول على وظيفة في غوغل.
الرئيس أوباما: الحق.
>> إريك شميدت: لدينا أسئلة، ونسأل المرشحين أسئلتنا،
وهذا هو واحد من لاري شويمر.
>> الرئيس أوباما: OK.
>> إريك شميدت: ماذا؟
اعتقد يا رفاق أنا تمزح؟
انها هنا.
ما هي الطريقة الأكثر فعالية ل فرز الأعداد الصحيحة مليون 32 بت؟
>> الرئيس أوباما: Well--
إريك شميدت: في بعض الأحيان، ربما أنا آسف، maybe--
الرئيس أوباما: لا، لا، لا، لا، لا، أنا think--
إريك شميدت: هذا ليس it--
الرئيس أوباما: I أعتقد، وأنا أعتقد أن فقاعة
سوف يكون نوعا بطريقة خاطئة للذهاب.
إريك شميدت: هيا.
الذي قال له هذا؟
حسنا.
لم أكن على علم الحاسوب on--
>> الرئيس أوباما: لقد حصلت جواسيس لدينا في هناك.
أستاذ: حسنا.
دعونا نترك وراءنا الآن العالم النظري للخوارزميات
في التحليل مقارب منه، والعودة إلى بعض الموضوعات
من أسبوع واحد صفر، وبدء لإزالة بعض عجلات التدريب،
اذا صح التعبير.
حتى يتسنى لك فهم حقا في نهاية المطاف من الألف إلى الياء، ما هو
يجري تحت غطاء محرك السيارة، عند كتابة وتجميع، وتنفيذ البرامج.
أذكر على وجه الخصوص، أن هذا كان برنامج C الأولى التي نظرت،
لذلك، برنامج بسيط الكنسي من نوع ما، نسبيا،
حيث، فإنه يطبع، مرحبا العالم.
وأذكر أنني قلت، عملية أن شفرة المصدر يمر
هذا هو بالضبط.
كنت تأخذ الكود الخاص بك، وتمرير من خلال مترجم، مثل رنة،
ويأتي من رمز الكائن، أن قد تبدو هذه، وتلك الأصفار
أن وحدة المعالجة المركزية للكمبيوتر، وسط وحدة المعالجة أو الدماغ،
تدرك في نهاية المطاف.
>> وتبين أن هذا هو قليلا من التبسيط،
أننا الآن في موقف لندف بصرف النظر
لفهم ما كان حقا يجري تحت غطاء محرك السيارة
في كل مرة تقوم بتشغيل رنة، أو بصورة أعم،
كل مرة تقوم فيها البرنامج، باستخدام واتخاذ CF 50 IDE.
على وجه الخصوص، أشياء من هذا القبيل هذا يتم إنشاؤها لأول مرة،
عند أول تجميع البرنامج.
وبعبارة أخرى، عند تأخذ شفرة المصدر الخاصة بك
وترجمة ذلك، ما هو أول يجري أنتج بواسطة رنة
هو ما يعرف باسم رمز التجميع.
وفي الواقع، يبدو تماما مثل هذا.
>> ركضت أمر في سطر الأوامر في وقت سابق.
hello.c رنة العاصمة اندفاعة الصورة، وهذا إنشاء ملف
بالنسبة لي دعا hello.s، داخل منها بالضبط
هذه المحتويات، وقليلا أكثر أعلاه وأكثر من ذلك بقليل أدناه،
ولكن لقد وضعت عصيرا المعلومات هنا على الشاشة.
وإذا كنت تبحث عن كثب، سترى على الأقل بضع كلمات مألوفة.
لدينا الرئيسي في القمة.
لقد printf لأسفل في الوسط.
وعلينا أيضا أن مرحبا العالم مائل ن في الاقتباس في الأسفل.
>> وكل شيء هنا هو تعليمات مستوى منخفض جدا
أن وحدة المعالجة المركزية للكمبيوتر تفهم.
تعليمات وحدة المعالجة المركزية التي تحرك الذاكرة حولها، أن سلاسل تحميل من الذاكرة،
وفي نهاية المطاف، الطباعة الأشياء التي تظهر على الشاشة.
الآن ما يحدث على الرغم من بعد يتم إنشاء هذا رمز التجميع؟
في نهاية المطاف، قمت بذلك، في الواقع، لا يزال توليد رمز الكائن.
ولكن الخطوات التي حقا كان يحدث تحت غطاء محرك السيارة
تبدو أكثر قليلا من هذا القبيل.
يصبح شفرة المصدر رمز التجميع، وبعد ذلك يصبح رمز الكائن،
وكلام المنطوق هنا هي أنه عند ترجمة التعليمات البرمجية المصدر،
يخرج رمز التجميع، ثم عند تجميع رمز التجميع الخاص بك،
يخرج رمز الكائن.
>> الآن رنة هو السوبر متطورة، مثل الكثير من المجمعين،
وانها تفعل كل خطوة من هذه الخطوات معا، وذلك لا يعني بالضرورة
إخراج أي وسيط الملفات التي يمكنك ان ترى ذلك.
انها مجرد تجمع الأشياء، وهو مصطلح عام
يصف هذه العملية برمتها.
ولكن إذا كنت تريد حقا أن تكون خاصة، هناك
الكثير من يجري هناك كذلك.
>> ولكن دعونا نعتبر أيضا أنه حتى الآن هذا البرنامج السوبر بسيط، hello.c،
استدعاء دالة.
ودعا printf.
ولكن أنا لم أكتب printf، في الواقع، الذي يأتي مع ج، إذا جاز التعبير.
انها استدعاء وظيفة هذا أعلن في io.h القياسية، التي
هو ملف رأس، والتي هو موضوع سنقوم الواقع
يغوص أكثر عمقا قبل فترة طويلة.
لكن ملف الرأس يرافق عادة
بواسطة ملف الرمز، ملف شفرة المصدر، وذلك يشبه إلى حد كبير يوجد io.h. القياسية
>> قبل وقت ما، شخص ما، أو شخص ما، وكتب أيضا
ملف يسمى io.c القياسية، في التي التعاريف الفعلية،
أو تطبيقات printf، وعناقيد من الوظائف الأخرى،
مكتوبة في الواقع.
ذلك نظرا لأنه إذا اعتبرنا وجود هنا على اليسار، hello.c، أنه عندما
المترجمة، يعطينا hello.s، حتى لو رنة لا يكلف نفسه عناء إنقاذ في مكان
يمكننا أن نرى ذلك، وهذا رمز التجميع يحصل تجميعها في hello.o، التي
هو، في الواقع، الاسم الافتراضي نظرا كلما تجميع المصدر
رمز إلى رمز الكائن، ولكنها ليست على استعداد تام لتنفيذ ذلك حتى الآن،
لأن خطوة أخرى يجب أن يحدث، ولديه
ويحدث للقلة الماضي أسابيع، وربما دون علم لك.
>> على وجه التحديد في مكان ما في CS50 IDE، وهذا،
جدا، وسوف يكون قليلا من التبسيط لحظة،
هناك، أو كان في قديم الزمان، ملف يسمى io.c القياسية،
أن شخصا ما جمع في io.s القياسية أو ما يعادلها،
أن شخصا تجميعها ثم في io.o القياسية،
أو اتضح في ملف مختلف قليلا
الشكل الذي يمكن أن يكون مختلفا ملف تمديد تماما،
لكن من الناحية النظرية والمفاهيمية، بالضبط كانت تلك الخطوات أن يحدث بشكل أو بآخر.
وهو ما يعني، أن الآن عندما أكتب برنامج،
hello.c، أن يقول فقط، مرحبا العالم، وأنا باستخدام كود شخص آخر
مثل printf، الذي كان مرة واحدة بناء على الوقت في ملف يسمى io.c القياسية،
ثم ما لدي لاتخاذ بلدي رمز الكائن، يا الأصفار ومنها،
وجوه هذا الشخص رمز، أو الأصفار ومنها،
وتصل بطريقة أو بأخرى منها معا في الملف النهائي واحدة، ودعا مرحبا، أن
لديه كل الأصفار و من وجهة نظري تلك الوظيفة الرئيسية،
وجميع من الأصفار وتلك لprintf.
>> والواقع، أن عملية الأخيرة ودعا، ربط رمز الكائن الخاص بك.
خرج منها هو ملف تنفيذي.
وذلك في الإنصاف، في نهاية اليوم، لا شيء
لقد تغيرت منذ أسبوع واحد، ونحن عندما بدأت لأول مرة تجميع البرامج.
والواقع أن كل هذا يحدث تحت غطاء محرك السيارة،
ولكن نحن الآن في موقف حيث يمكننا فعلا
ندف عدا هذه الخطوات المختلفة.
وبالفعل، في نهاية اليوم، نحن لا نزال
اليسار مع الأصفار وتلك التي هو في الواقع سغ] كبير الآن
لقدرة أخرى من C، أن لقد يكن لدينا للاستفادة الأرجح
حتى الآن، والمعروفة باسم مشغلي المختصة بالبت.
وبعبارة أخرى، حتى الآن، في أي وقت قمنا التعامل مع البيانات في C أو C المتغيرات في،
لقد كان لدينا أشياء مثل حرف والعوامات والإضافية
ويتوق والزوجي وما شابه ذلك، ولكن كل من هؤلاء كانوا من ثمانية بت على الأقل.
لقد الاطلاق حتى الآن قادرة على تلاعب بت الفردية،
على الرغم من بعض الشيء الفردي، ونحن أعرف، يمكن أن تمثل 0 و 1.
الآن اتضح أنه في C، كنت يمكن الحصول على بت الفردية،
إذا كنت تعرف بناء الجملة، التي للحصول عليهم.
>> لذلك دعونا نلقي نظرة في مشغلي المختصة بالبت.
حتى في الصورة هنا بعض الرموز التي قمنا، من نوع، نوعا ما، يشاهد من قبل.
أرى العطف، عمودي بار، والبعض الآخر كذلك،
ونذكر بأن العطف العطف شيء رأيناه من قبل.
والعامل المنطقي AND، حيث لديك اثنين منهم معا، أو المنطقية OR
المشغل، حيث كنت دينا اثنين من أشرطة عمودية.
مشغلي المختصة بالبت، والتي سنقوم رؤية تعمل على بت على حدة،
مجرد استخدام العطف واحد، شريط عمودي واحد، ورمز الإقحام
يأتي بعد ذلك، وقليلا تيلدا، وغادر بعد ذلك
قوس يقم قوس، أو قوس الصحيح قوس الصحيح.
كل هذه لها معان مختلفة.
>> في الواقع، دعونا نلقي نظرة.
دعنا نذهب المدرسة القديمة اليوم، واستخدام شاشة تعمل باللمس من الأمس،
المعروفة باسم لوحة بيضاء.
وهذه لوحة بيضاء سوف تسمح لنا
للتعبير عن بعض الرموز بسيطة إلى حد ما، أو بالأحرى بعض صيغ بسيطة إلى حد ما،
ما في وسعنا ثم في نهاية المطاف الرافعة المالية، من أجل
للوصول فرد بت ضمن برنامج C.
وبعبارة أخرى، دعونا نفعل هذا.
دعونا نتحدث أولا ل لحظة عن العطف،
وهو أحادي المعامل AND المشغل.
وبعبارة أخرى، وهذا هو المشغل الذي يسمح
لي أن يكون متغير الأيسر عادة، ومتغير الأيمن،
أو قيمة الفردية، أننا إذا AND معا، يعطيني النتيجة النهائية.
فماذا يعني؟
إذا كان في البرنامج، يكون لديك متغير أن مخازن واحدة من هذه القيم،
أو دعونا يبقيه بسيط، وفقط كتابة الأصفار ومنها على حدة،
وهنا كيف يعمل المشغل العطف.
0 الضم 0 سوف تساوي 0.
الآن لماذا هذا؟
>> انها تشبه الى حد بعيد التعبيرات المنطقية،
أن ناقشناه حتى الآن.
إذا كنت تعتقد بعد كل شيء، و0 غير كاذبة، 0 غير صحيح، كاذبة وزائفة
هو، كما ناقشناه منطقيا، كاذبة أيضا.
حتى نحصل 0 هنا كذلك.
إذا كنت تأخذ 0 العطف 1، بالاضافة الى انه، ايضا،
سيكون 0، لأن لهذا التعبير الأيسر ليكون صحيحا أو 1،
أنها تحتاج إلى أن يكون صحيحا وصحيح.
ولكن هنا لدينا كاذبة وصحيح، أو 0 و 1.
الآن مرة أخرى، إذا كان لدينا 1 العطف 0، وهذا، أيضا، سيكون 0،
وإذا كان لدينا 1 العطف 1، أخيرا هل لدينا 1 بت.
لذلك وبعبارة أخرى، نحن لا نفعل أي شيء للاهتمام مع هذا المشغل
فقط حتى الآن، هذا المشغل العطف.
انها أحادي المعامل AND المشغل.
ولكن هذه هي المكونات عبر التي يمكن أن نفعله
أشياء مثيرة للاهتمام، كما سنرى في وقت قريب.
>> الآن دعونا ننظر إلى مجرد واحد شريط عمودي هنا على اليمين.
إذا كان لدي 0 قليلا وأنا أو مع، المختصة بالبت
أو المشغل، 0 نوعا آخر، هذا سوف تعطيني 0.
إذا كنت تأخذ 0 قليلا وأو مع 1 قليلا، ثم انا ذاهب الى الحصول على 1.
في واقع الأمر، فقط ل وضوح، واسمحوا لي أن أعود،
بحيث بلدي أشرطة عمودية لا مخطئا ل1 ل.
اسمحوا لي إعادة كتابة كل بلدي 1 هو أكثر من ذلك قليلا
بشكل واضح، بحيث نرى المقبل، إذا أنا و1 أو 0، وهذا سيكون 1،
وإذا كان لدي 1 OR 1 أن، أيضا، سوف تكون 1.
حتى تستطيع أن ترى منطقيا أن OR مشغل تتصرف بشكل مختلف للغاية.
هذا يعطيني 0 أو 0 يعطيني 0، ولكن كل تركيبة أخرى يعطيني 1.
طالما أنا واحد 1 في الصيغة، فإن النتيجة ستكون 1.
>> على النقيض من ذلك مع و المشغل، والعطف،
فقط إذا كان لدي اثنين من 1 في المعادلة، هل فعلا الحصول على 1 خارج.
الآن هناك عدد قليل آخر مشغلي كذلك.
واحد منهم هو أكثر من ذلك بقليل المعنيين.
لذلك اسمحوا لي المضي قدما ومحو هذا لتحرير بعض المساحة.
ودعونا نلقي نظرة على رمز الإقحام، لمجرد لحظة.
هذا هو عادة شخصية يمكنك كتابة
على جهاز التحول عقد لوحة المفاتيح و ثم أحد الأرقام فوق الولايات المتحدة الخاص بك
لوحة المفاتيح.
>> لذلك هذا هو الحصري أو المشغل الحصري OR.
لذلك رأينا فقط المشغل OR.
هذا هو الحصري أو المشغل.
ما هو في الواقع الفرق؟
حسنا دعونا ننظر فقط في الصيغة، واستخدام هذه المكونات في نهاية المطاف.
0 XOR 0.
أنا سأقول دائما 0.
هذا هو تعريف XOR.
0 XOR 1 سيكون 1.
1 XOR 0 سيكون 1، و1 XOR 1 سيكون؟
الخطأ؟
صحيح؟
لا اعرف.
0.
الآن ما الذي يجري هنا؟
كذلك التفكير في اسم هذا المشغل.
OR خاص، وذلك ل الاسم والنوع، يقترح،
الجواب لن يؤدي الا الى أن 1 إذا كانت المدخلات هي حصرية،
تختلف حصرا.
حتى هنا المدخلات هي نفسه، وبالتالي فإن الناتج هو 0.
هنا المدخلات هي نفسه، وبالتالي فإن الناتج هو 0.
وهنا هي النواتج مختلفة، فإنها تعود حصرا، وبالتالي فإن الناتج هو 1.
لذلك فمن تشبه الى حد بعيد و، انها متشابهة جدا،
أو بالأحرى انها تشبه الى حد بعيد OR، ولكن فقط بطريقة حصرية.
هذا واحد لم يعد 1، لأن لدينا اثنين 1، و
وليس على سبيل الحصر، واحد منهم فقط.
حسنا.
ماذا عن الآخرين؟
حسنا تيلدا، وفي الوقت نفسه، هو لطيفة فعلا وبسيطة، والحمد لله.
وهذا هو أحادي المشغل، مما يعني
انها تطبق على مدخل واحد فقط، المعامل واحد، إذا جاز التعبير.
ليس إلى اليسار واليمين.
وبعبارة أخرى، إذا كنت تأخذ من تيلدا 0، فإن الإجابة ستكون عكس ذلك.
وإذا كنت تأخذ تيلدا من 1، والجواب سيكون هناك عكس ذلك.
وبالتالي فإن المشغل هو تيلدا وسيلة لإنكار بعض الشيء،
أو التقليب قليلا من 0-1، أو 1-0.
>> وأن يترك لنا أخيرا مع اثنين فقط من المشغلين النهائية،
ما يسمى التحول الأيسر، و ما يسمى حق مشغل التحول.
دعونا نلقي نظرة على كيفية عمل تلك.
المشغل تحول اليسار، وكتب مع اثنين من أقواس زاوية من هذا القبيل،
يعمل على النحو التالي.
إذا كان لي المدخلات، أو بلدي المعامل، وإلى اليسار مشغل التحول هو بكل بساطة 1.
وI ثم يقول الكمبيوتر ل غادر التحول أن 1، ويقول سبعة أماكن،
والنتيجة هي كما لو كنت أخذ ذلك 1، وتحريكه
سبعة أماكن على ل اليسار، وبشكل افتراضي،
ونحن في طريقنا لنفترض أن مساحة لليمين
سوف يتم مبطن مع الأصفار.
وبعبارة أخرى، 1 غادر تحول 7 تسير أن تعطيني أن 1، تليها 1، 2، 3،
4، 5، 6، 7 الأصفار.
حتى بطريقة ما، فإنه يسمح لك ل اتخاذ عدد صغير مثل 1،
وجعل من الواضح أنه كثيرا من ذلك بكثير، أكبر بكثير في هذا السبيل،
لكننا ذاهبون فعلا أن نرى نهج أكثر ذكاء لذلك
بدلا من ذلك، وكذلك،
>> حسنا.
هذا كل شيء لثلاثة أسابيع.
سوف نرى لك في المرة القادمة.
كان هذا CS50.
>> [عزف الموسيقى]
>> رئيس 1: كان على وجبة خفيفة منع تناول مثلجات حلوى ساخنة.
كان لديه كل شيء على وجهه.
كان يرتدي أن الشوكولاته مثل لحية
المتحدث 2: ماذا تفعل؟
SPEAKER 3: هممم؟
ماذا؟
>> المتحدث 2: هل مجرد ركود مزدوج؟
أنت تراجع مزدوج الشريحة.
SPEAKER 3: عفوا.
المتحدث 2: أنت تراجع رقاقة، كنت أخذت لدغة، وأنت انخفض مرة أخرى.
SPEAKER 3:
المتحدث 2: هذا هو مثل وضع الخاص بك كامل الحق الفم في تراجع.
في المرة القادمة كنت تأخذ شريحة، مجرد تراجع لمرة واحدة، ووضع حد لها.
>> SPEAKER 3: هل تعرف ما هي، دان؟
أنت تراجع بالطريقة التي تريدها الى الانخفاض.
سوف تراجع الطريقة التي أريد أن الانخفاض.