المفضلة لديك خوارزمية والدرس علمك [مغلقة]

https://stackoverflow.com/questions/26301

09-06-2019
|

سؤال

ما خوارزمية علمك أكثر عن البرمجة أو لغة معينة الميزة ؟

لدينا جميعا تلك اللحظات حيث فجأة ونحن نعلم فقط أعلم ، لقد تعلمنا درسا هاما للمستقبل على أساس أخيرا فهم خوارزمية كتبها مبرمج بضع خطوات حتى التطورية سلم.الذي أفكار مدونة لمسة سحرية ؟

المحلول

"تكرار هو الإنسان ، recurse الإلهية" - نقلت في عام 1989 في الكلية.

P. S.أرسلت بواسطة Woodgnome في انتظار دعوة للانضمام

نصائح أخرى

العامة الخوارزميات:

فرز سريع (وهو متوسط تعقيد التحليل) ، يدل على أن العشوائي المدخلات الخاصة بك يمكن أن يكون شيئا جيدا!;
متوازنة الأشجار (AVL الأشجار على سبيل المثال) ، أنيق طريقة التوازن البحث/إدراج التكاليف ؛
الخاص ديكسترا و فورد-Fulkerson خوارزميات على الرسوم البيانية (أنا أحب حقيقة أن الثاني لديه العديد من التطبيقات) ؛
منطقة الهبوط* الأسرة من خوارزميات الضغط (LZW على سبيل المثال) ، ضغط البيانات بدا نوع من السحر لي حتى اكتشفت أنه (منذ وقت طويل) );
على الاتحاد الفرنسي للتنس, كل مكان (إعادة استخدامها في العديد من خوارزميات أخرى);
على البسيط الخوارزمية ، في كل مكان أيضا.

العددية ذات الصلة:

اقليدس خوارزمية لحساب gcd اثنين من الاعداد الصحيحه:واحدة من أول خوارزميات بسيطة وأنيقة, قوية, لديه الكثير من التعميمات;
سريع الضرب من الاعداد الصحيحه (كولي-Tukey على سبيل المثال) ؛
نيوتن التكرار لعكس / العثور على جذر قوي جدا الفوقية الخوارزمية.

عدد من الناحية النظريه ذات الصلة:

AGM-ذات خوارزميات (أمثلة):يؤدي إلى بسيطة جدا وأنيقة خوارزميات لحساب بي (وأكثر من ذلك بكثير!), على الرغم من أن نظرية عميقة جدا (غاوس عرض الوظائف الاهليلجيه وحدات نماذج من ذلك ، لذلك يمكن القول أن أنجبت معادلات حدوديه...);
على عدد مجال غربال (على صحيح التعميل): جدا معقدة جدا لطيفة النظرية نتيجة (وهذا ينطبق أيضا AKS الخوارزمية التي أثبتت أن يعبي في P).

كما يتمتع دراسة الحوسبة الكمومية (الشور و Deutsch-Josza خوارزميات على سبيل المثال):هذا يعلمك التفكير في الخروج من مربع.

كما يمكنك أن ترى, أنا منحاز قليلا نحو الرياضيات المنحى الخوارزميات :)

فلويد-Warshall جميع أزواج أقصر مسارات الخوارزمية

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

هنا هو السبب في أنه cool:عندما تقوم أولا معرفة أقصر مسار المشكلة في نظرية الرسم البياني الحال ، ربما تبدأ مع الخاص ديكسترا خوارزمية أن يحل واحد-المصدر أقصر طريق.انها معقدة جدا في البداية ولكن يمكنك الحصول على أكثر من ذلك ، هل يفهم بشكل كامل.

ثم قال المعلم "نحن الآن نريد حل نفس المشكلة ولكن كل مصادر".تظن نفسك "يا إلهي, هذا سيكون أصعب بكثير المشكلة! سيكون على الأقل N مرات أكثر تعقيدا مما الخاص ديكسترا خوارزمية!!!".

ثم المعلم يعطيك فلويد-Warshall.و عقلك ينفجر.ثم البدء في تمزيق في كيفية جميل بسيط الخوارزمية.انها مجرد ثلاثة أسباب-حلقة متداخلة.يستخدم فقط بسيطة مجموعة لها بنية البيانات.

الأكثر فتح العين جزء بالنسبة لي هو ما يلي تحقيق:نقول لديك حل مشكلة A.ثم لديك أكبر "superproblem" ب الذي يحتوي على المشكلة A.حل مشكلة ب في الواقع قد يكون أبسط من حل المشكلة A.

فرز سريع.لقد أظهرت لي أن العودية يمكن أن تكون قوية ومفيدة.

هذا قد يبدو تافهة ولكن كان الوحي بالنسبة لي في ذلك الوقت.كنت في أول الطبقة البرمجة(VB6) و الأستاذ قد علمنا عن أرقام عشوائية وأعطى التعليمات التالية:"خلق الظاهري آلة اليانصيب.تخيل الكرة الزجاجية الكاملة من 100 كرات بينغ بونغ علامة من 0 إلى 99.اختيار بشكل عشوائي و عرض عددهم حتى تم اختيارها لا مكررة."

الجميع بكتابة برنامج مثل هذا:اختيار الكرة ، وضع رقمه في "بالفعل قائمة مختارة" ومن ثم اختيار كرة أخرى.تحقق لمعرفة ما إذا كان محددا بالفعل ، إذا so كرة أخرى ، إذا لم يضع رقمه على "بالفعل قائمة مختارة" الخ....

بالطبع بنهاية كانوا يصنعون مئات من المقارنات إلى العثور على عدد قليل من الكرات التي لم بالفعل تم انتقاؤها.كان مثل رمي الكرات مرة أخرى في جرة بعد اختيار لهم.بلدي الوحي إلى رمي الكرات بعيدا بعد حصوله.

أعرف أن هذا يبدو العقل بتخدير واضحة ولكن هذه كانت اللحظة التي "برمجة مفتاح" حصلت انقلبت في رأسي.هذه كانت اللحظة التي البرمجة ذهب من يحاول تعلم لغة أجنبية غريبة إلى محاولة معرفة ممتعة لغز.ومرة واحدة لقد جعلت العقلية العلاقة بين البرمجة و متعة كان هناك حقا لا وقف لي.

Huffman coding سيكون لي كان في الأصل بلدي غبي النسخة عن طريق التقليل من عدد من بت لترميز النص من 8 إلى أسفل إلى أقل, ولكن لم يفكر متغير عدد البتات اعتمادا على تردد.ثم وجدت huffman coding وصفها في مقال في مجلة و فتحت الكثير من الاحتمالات الجديدة.

Bresenham خط رسم خوارزمية حصلت لي مهتمة في الوقت الحقيقي الرسومات.وهذا يمكن أن تستخدم لتقديم شغل المضلعات مثل المثلثات ، لأشياء مثل 3D نموذج التقديم.

عودي تحليل النسب - أتذكر أنني كنت معجب جدا كيف هذا كود بسيط يمكن أن تفعل شيئا على ما يبدو معقدة.

فرز سريع في هاسكل:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

على الرغم من أنني لم يكتب هاسكل في ذلك الوقت ، لم أفهم هذا الرمز و مع ذلك العودية و فرز سريع الخوارزمية.فقط انقر...و كان

تكرارية خوارزمية فيبوناتشي ، لأنه بالنسبة لي أنه مسمر حقيقة أن الأكثر أناقة رمز (في هذه الحالة ، العودية الإصدار) ليست بالضرورة الأكثر كفاءة.

وضع - في "أكذوبة(10) = fib(9) + fib(8)" النهج يعني أن أكذوبة(9) وسيتم تقييم إلى أكذوبة(8) + fib(7).حتى تقييم fib(8) (و لذلك fib7, fib6) سوف تكون جميع تقييمها مرتين.

الطريقة التكرارية, (داء = prev1 + prev2 في forloop) لا شجرة من هذا الطريق ، كما أنها لا تأخذ الكثير من الذاكرة لأنه فقط 3 عابرة المتغيرات بدلا من n إطارات في العودية المكدس.

أنا أميل إلى السعي بسيطة, أنيقة رمز عندما أكون البرمجة, ولكن هذه هي الخوارزمية التي ساعدتني ندرك أن هذه ليست النهاية-على جميع لكتابة البرامج الجيدة و التي في نهاية المطاف للمستخدمين النهائيين لا يهمني كيف الكود الخاص بك يبدو.

لسبب ما مثل Schwartzian تحويل

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

حيث فو($) يمثل حوسبة كثيفة التعبير أن يأخذ $ (كل بند من بنود القائمة بدوره) وتنتج القيمة المقابلة التي سيتم مقارنة من أجلها.

Minimax علمني أن برامج الشطرنج ليست الذكية ، فإنها يمكن أن مجرد التفكير في المزيد من التحركات المقبلة مما تستطيع.

أنا لا أعرف إذا كان هذا يؤهل خوارزمية ، أو مجرد الكلاسيكية هاك.في كلتا الحالتين, أنه يساعد على الحصول على لي أن أبدأ التفكير خارج الصندوق.

مبادلة 2 الصحيحه دون استخدام وسيطة المتغير (C++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

فرز سريع:حتى وصلت إلى الكلية, لم وتساءل عما إذا كانت القوة الغاشمة فقاعة نوع كانت الطريقة الأكثر فعالية نوعا ما.بدت واضحة بشكل حدسي.ولكن التعرض غير واضحة حلول مثل فرز سريع علمني أن ننظر إلى الماضي الحلول واضحة لمعرفة إذا كان أفضل شيء هو متاح.

بالنسبة لي انها ضعيفة-heapsort خوارزمية لأنه يظهر (1) كم من الحكمة اختيار هيكل البيانات (و خوارزميات تعمل على ذلك) يمكن أن تؤثر على أداء و (2) أن الأشياء الرائعة التي يمكن اكتشافها حتى في القديمة المعروفة الأشياء.(ضعيف-heapsort هو الخيار الأفضل من كل كومة أنواع ، الذي كان ثبت ثماني سنوات في وقت لاحق.)

هذا هو واحد بطيء :)

تعلمت الكثير عن كل من C و أجهزة الكمبيوتر بشكل عام من خلال فهم Duffs الجهاز و XOR مقايضة

تحرير:

@جيسون Z, أن XOR مبادلة :) رائع أليس كذلك.

لسبب فقاعة نوع لطالما وقفت لي.ليس لأنها أنيقة أو جيد فقط لأنه لديه/لديها جوفي اسم أفترض.

ليس لدي المفضلة -- هناك الكثير من تلك الجميلة للاختيار من بينها -- ولكن واحد لقد وجدت دائما مثيرة للاهتمام هو بيلي–Borwein–بلوف (BBP) صيغة, التي تمكنك من حساب التعسفي أرقام من بي دون معرفة الأرقام السابقة.

RSA أدخلني إلى عالم من وحدات الحساب التي يمكن استخدامها حل a الدهشة عدد من مثيرة للاهتمام مشاكل!

لم علمني الكثير ، ولكن جونسون–تروتر الخوارزمية لم يفشل ضربة ذهني.

ثنائي المخططات القرار, رغم رسميا لا خوارزمية ولكن datastructure ، يؤدي إلى أنيقة الحد الأدنى من الحلول لمختلف أنواع (منطقية) logic المشاكل.كانوا اخترع يعدون للحد من باب الاعتماد في رقاقة التصميم, و يمكن أن ينظر إليها باعتبارها واحدة من الأساس من السيليكون الثورة.مما أدى خوارزميات بسيطة بشكل مثير للدهشة.

ما علموني:

المدمجة تمثيل أي المشكلة المهم ؛ صغيرة جميلة
مجموعة صغيرة من القيود/تخفيضات تطبيقها بشكل متكرر يمكن استخدامها لتحقيق ذلك
مشاكل مع التماثلات, tranformation إلى النموذج المتعارف عليه أن تكون الخطوة الأولى للنظر في
ليس كل قطعة من الأدب هو قراءة.كانوث اكتشفت BDD عدة سنوات بعد اختراع/مقدمة.(وقضى سنة تقريبا التحقيق معهم)

بالنسبة لي مبادلة بسيطة في كيلي & بول هو كتاب عن ج إلى إظهار الدعوة من قبل المرجع انقلبت لي عندما رأيت لأول مرة.نظرت في ذلك ، مؤشرات قطعت في المكان.الحرفية...

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

على أبراج هانوي الخوارزمية هي واحدة من أجمل الخوارزميات.انه يظهر كيف يمكن استخدام العودية إلى حل مشكلة ما بطريقة أكثر الأزياء الأنيقة من أسلوب التكرار.

بدلا من ذلك ، العودية خوارزمية فيبوناتشي سلسلة حساب صلاحيات عدد إثبات عكس حالة متكررة الخوارزمية المستخدمة من أجل عودية بدلا من توفير قيمة جيدة.

تكرارية خوارزمية فيبوناتشي ، لأنه بالنسبة لي أنه مسمر حقيقة أن الأكثر أناقة رمز (في هذه الحالة ، العودية الإصدار) ليست بالضرورة الأكثر كفاءة.

الطريقة التكرارية, (داء = prev1 + prev2 في forloop) لا شجرة من هذا الطريق ، كما أنها لا تأخذ الكثير من الذاكرة لأنه فقط 3 عابرة المتغيرات بدلا من n إطارات في العودية المكدس.

أنت تعرف أن فيبوناتشي وقد شكل مغلق حل يسمح المباشر في حساب النتيجة في عدد محدد من الخطوات ، أليس كذلك ؟ وهي (phiⁿ - (1 - phi)ⁿ) / الجذر التربيعي(5).كان دائما يبدو لي نوعا ما لافتا أن هذا ينبغي أن تسفر عن عدد صحيح, ولكنه لا يفعل.

فاي هو النسبة الذهبية ، بالطبع ، (1 + sqrt(5)) / 2.

خوارزمية التي يولد قائمة يعبي بمقارنة كل رقم إلى القائمة الحالية يعبي, مضيفا أنه إذا كان لم يتم العثور على وإعادة قائمة يعبي في نهاية المطاف.العقل والانحناء بطرق عدة ، ليس أقلها كونه فكرة استخدام جزئيا الانتهاء الإخراج الأساسي معايير البحث.

تخزين اثنين من المؤشرات في كلمة واحدة على قائمة مرتبطة على نحو مضاعف علمتني الدرس الذي يمكنك أن تفعل أشياء سيئة جدا في C في الواقع (مع المحافظة GC سوف يكون الكثير من المتاعب).

الأكثر فخور لقد تم الحل هو كتابة شيء مشابه جدا DisplayTag الحزمة.علمتني الكثير عن مدونة تصميم الصيانة وإعادة استخدامها.كتبت جيدا قبل DisplayTag ، وكان غرقت في التجمع الوطني الديمقراطي الاتفاق ، لذلك لم أستطع فتح مصدر ذلك, ولكن لا يزال يمكنني التحدث gushingly عن ذلك في مقابلات العمل.

خريطة/الحد.اثنين من المفاهيم البسيطة التي تناسب معا لجعل تحميل البيانات-معالجة المهام أسهل يوازي.

أوه...وانها فقط على أساس واسع موازية الفهرسة:

http://labs.google.com/papers/mapreduce.html

ليس المفضل لدي ، ولكن ميلر رابين الخوارزمية لاختبار بريماليتي أظهرت لي أن يجري الحق طوال الوقت تقريبا, هو جيد بما فيه الكفاية طوال الوقت تقريبا.(أيلا الثقة إحتمالات خوارزمية فقط بسبب احتمال أن تكون خاطئة.)

@كريشنا كومار

جميع الحل هو أكثر متعة من حل العودية.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow