الفنون رقم 023

الفنون 023

هذه المادة 23

سؤال خوارزمية الخوارزمية

72. تعديل المسافة

صعوبة صعبة

بمعرفة كلمتين word1 و word2، أوجد أقل عدد من العمليات المطلوبة لتحويل word1 إلى word2.

لديك العمليات الثلاث التالية المسموح بها على الكلمة:

مثال 1:

مثال 2:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

لم أحل هذا السؤال بالكامل بنفسي. ثم بحثت عن الإجابة ووجدت أن البرمجة الديناميكية مطلوبة. لم أدرس البرمجة الديناميكية بعمق من قبل. انتهزت هذه الفرصة لدراستها بعناية ووجدت أن البرمجة الديناميكية ليس من السهل فهمها حقًا. بعد قراءته لمدة يومين، وجدت أنني قد بدأت للتو. عند تعلم البرمجة الديناميكية، يوصى بقراءة “توضيح الخوارزمية” أولاً. من السهل نسبيًا فهم شرح البرمجة الديناميكية في Algorithm Illustration، ثم ابحث عن معلومات على الإنترنت لمساعدتك على الفهم. البرمجة الديناميكية ليست شيئًا يمكن فهمه دفعة واحدة. لا تزال بحاجة إلى ممارسة المزيد.

فيما يتعلق بسؤال الخوارزمية هذا، هذا السؤال جيد نسبيًا: https://blog.csdn.net/pipisorry/article/details/46383947

بالإضافة إلى البرمجة الديناميكية، يمكن أيضًا حل هذه المشكلة بشكل متكرر.

الحل

اللغة: ج

static inline int min(int a, int b)
{
    return a < b ? a : b;
}

 int minDistance(char* word1, char* word2)
{
    int i, j;
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int *table = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    int **dp = malloc((len1 + 1) * sizeof(int *));
    for (i = 0; i < len1 + 1; i++) {
        dp[i] = table + i * (len2 + 1);
    }
    
    for (i = 0; i < len2 + 1; i++) {
        dp[0][i] = i;
    }
    for (i = 0; i < len1 + 1; i++) {
        dp[i][0] = i;
    }
    
    for (i = 1; i < len1 + 1; i++) {
        for (j = 1; j < len2 + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            }
            

        }
    }
    return dp[len1][len2];
}

مراجعة

تقدم هذه المقالة بشكل أساسي العديد من المعارف البرمجية الأساسية التي يجب على مبتدئي البرمجة إتقانها: https://dandan2009.github.io/2019/01/25/the-main-pillars-of-learning-programming/

نصائح

لقد قمنا هذا الأسبوع بفرز مبادئ التشفير غير المتماثل وتوقيعات https وiOSAPP: https://dandan2009.github.io/2019/01/24/certificate-rsa/

شارك

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