Page 1 of 3 123 LastLast
Results 1 to 25 of 67

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197

    Chars property â C#

    Ìîæå ëè íÿêîé äà ìè êàæå òîâà property Chars èìà ëè ãî â C# èëè å íàëè÷íî ñàìî âúâ VB?

    Ñúùî äà ïîïèòàì íåùî çà êà÷åñòâàòà íà òàçè êíèãà íà MICHAEL MCMILLAN.

    DATA STRUCTURES AND
    ALGORITHMS USING C#

    Ïðèìåðíèòå êîäîâå áúêàò îò ñèíòàêòè÷íè ãðåøêè è íå ìîãà äà ïóñíà åäèí ïðèìåð êàòî õîðàòà.
    Last edited by jordan17772; 15th December 2009 at 14:29.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  2. #2
    Âåãàí íà ìåñíà äèåòà XaMaB's Avatar
    Join Date: Nov:2001
    Location: Ñîôèÿ
    Posts: 20,387
    Ïîñëåäíà ðåäàêöèÿ: èçâúðøåíà îò XaMaB; íà äíåøíà äàòà. 0.42 ñåêóíäè ñëåä ïóñêàíå íà ïîñòà

    In God we Trust (all others must submit a X.509 certificate). Àêî ñïîðèø ñ èäèîò, âåðîÿòíî è òîé ïðàâè ñúùîòî èëè ñè ïîïàäíàë íà ïàðòèåí (íåïúëåí) ÷ëåí

  3. #3
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Òúêìî ñè âúâåæäàì ïðèìåðà â òåìàòà äèíàìè÷íî ïðîãðàìèðàíå, çà íàìèðàíå íàé-ãîëÿì ïîäíèç ìåæäó íÿêîëêî. È õîï, ïèøà ñâîéñòâîòî Chars è intellisense íå çàöåïâà. Äèðåêòèâàòà using System ñúì ÿ ïèñàë. Ñòðàííî. Ïî-íàòàòúê â êîäà ïúê èìàøå óñëîâåí oïåðàòîð if (warr1[i] = warr2[j]), êîéòî íå å âúçìîæíî äà âúðíå áóëåâ îòãîâîð, çàðàäè =, âìåñòî ==. Ñúùî òàêà, ïîñëå for ñ äâå ñåêöèè èíèöèàëèçàöèÿ è óñëîâåèå ïðè ëèïñâà ÷àñòà ñ èòåðàöèÿòà. Ïðîñòî èìà åäíà òî÷êà è çàïåòàÿ äà ïîÿñíÿ çàùî ñå èçíåðâèõ. Êíèãà èçäàâàíà îò CAMBRIDGE UNIVERSITY PRESS, à ïúëíà ñ òàêúâ óæàñåí êîä.

    static void LCSubstring(string word1, string word2, string[] warr1, string[] warr2, int[,] arr)
    {

    int len1, len2;
    len1 = word1.Length;
    len2 = word2.Length;
    for (int k = 0; k <= word1.Length - 1; k++)
    {
    warr1[k] = word1.Chars(k); <-- òî÷íî òóê èäâà ïðîáëåìà. Ëèïñâà òîâà ñâ-âî. Äà íå áè äà å ïðåìàõíàòî ñëåä C# 2.0

    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	17.jpg‎ 
Views:	491 
Size:	192.5 KB 
ID:	25941  
    Last edited by jordan17772; 15th December 2009 at 15:19.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  4. #4
    Âåãàí íà ìåñíà äèåòà XaMaB's Avatar
    Join Date: Nov:2001
    Location: Ñîôèÿ
    Posts: 20,387
     ëèíêà ïî-ãîðå òî÷íî ñè å îïèñàíî ÷å òîâà ïðîïúðòè ãî èìàø ñàìî âúâ VB.
    çà Ö-ðåøåòêà òè å warr1[k] = word1[k]
    Ïîñëåäíà ðåäàêöèÿ: èçâúðøåíà îò XaMaB; íà äíåøíà äàòà. 0.42 ñåêóíäè ñëåä ïóñêàíå íà ïîñòà

    In God we Trust (all others must submit a X.509 certificate). Àêî ñïîðèø ñ èäèîò, âåðîÿòíî è òîé ïðàâè ñúùîòî èëè ñè ïîïàäíàë íà ïàðòèåí (íåïúëåí) ÷ëåí

  5. #5
    Registered User ñèìî's Avatar
    Join Date: Feb:2006
    Location: Âàðíà
    Posts: 653
    È àç íå îòêðèâàì òàêúâ ìåòîä.
    Ïðîñòî çàìåíè òîâà:
    Code:
    warr1[k] = word1.Chars(k);
    ñ òîâà:
    Code:
    warr1[k] = word1[k];
    EDIT:

  6. #6
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Ìåðñè, ñåãà èçëèçà cannot implicitly convert type 'char' to 'string ' íî ùå âèäÿ êàê ùå ãî ïðåáîðÿ. Èìà è îùå åäíà íåäîìèñëèöà â êîäà, íî äà ÿ ñòèãíà è íåÿ.

    îôô òèÿ èíäåêñàòîðè, òåé ìå ìú÷àò...
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  7. #7
    Registered User ñèìî's Avatar
    Join Date: Feb:2006
    Location: Âàðíà
    Posts: 653
    Code:
    warr1[k] = word1[k].ToString();

  8. #8
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Quote Originally Posted by ñèìî View Post
    Code:
    warr1[k] = word1[k].ToString();
    Te òàêà äåáúãåðà ìúë÷è

    warr1[k] = Convert.ToString(word1[k]);
    Áîæå, áîæå...êàêâî ñà ïðàâèëè òèÿ òóêà

    static void DispArray(int arr[,]) {}

    âìåñòî static void DispArray(int[,] arr) {}
    Last edited by jordan17772; 15th December 2009 at 16:05.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  9. #9
    Registered User ñèìî's Avatar
    Join Date: Feb:2006
    Location: Âàðíà
    Posts: 653
    Âàðèàíòè èìà ïîíå îùå íÿêîëêî.

  10. #10
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Åé ãî öåëèÿ êîä, àêî íÿêîé ìîæå äà ãî ïîäêàðà, åâàëà. Ïðîñòî ïîäèãðàâêà ñ òèÿ ïðèìåðè â òàçè Âåëèêà òâîðáà íà Êåìáðè÷ ÞíèâúðñèòÈ Ïðåññ
    [I]

    using System;

    class chapter17
    {

    static void LCSubstring(string word1, string word2, string[] warr1, string[] warr2, int[,] arr)
    {

    int len1, len2;
    len1 = word1.Length;
    len2 = word2.Length;
    for (int k = 0; k <= word1.Length - 1; k++)
    {
    warr1[k] = Convert.ToString(word1[k]);
    warr2[k] = Convert.ToString(word2[k]);

    }

    for (int i = len1 - 1; i >= 0; i--)
    for (int j = len2 - 1; j >= 0; j--)
    if (warr1 == warr2[j])
    arr[i, j] = 1 + arr[i + 1, j + 1];
    else
    arr[i, j] = 0;

    }

    static string ShowString(int[,] arr, string[] wordArr)
    {

    string substr = "";

    for (int i = 0; i <= arr.GetUpperBound(0); )
    for (int j = 0; j <= arr.GetUpperBound(1); )
    if (arr[i, j] > 0)
    substr += wordArr[j];
    return substr;
    }

    static void DispArray(int[,] arr) {
    for (int row = 0; row <= arr.GetUpperBound(0); )
    for (int col = 0; col <= arr.GetUpperBound(1); )
    Console.Write(arr[row, col]);
    Console.WriteLine();

    }

    static void Main(){

    string word1 = "maven";
    string word2 = "havoc";
    string[] warray1 = new string[word1.Length];
    string[] warray2 = new string[word2.Length];
    string substr;
    int[,] larray = new int[word1.Length, word2.Length];
    LCSubstring(word1, word2, warray1,warray2, larray);

    Console.WriteLine();
    //DispArray(larray);

    substr = ShowString(larray, warray1);
    Console.WriteLine();
    Console.WriteLine("The strings are: " + word1 + " " + word2);

    // if (substr > "") Console.WriteLine("The longest comon substring is: " + substr);
    // else
    // Console.WriteLine("There is no comon substring");
    }
    }
    Òîâà òðÿáâà äà èçêàðâà



    Áëàãîäàðÿ çà ïîìîùà, íî òàÿ êíèãà õè÷ íå ìè ïîìîãíà, îñâåí ìíîãîòî íåäîìèñëèöè ïî 3,4 ïðèìåðà ñ êîèòî ìå îòêàçà äà ÿ ÷åòà.

    P.P Ìîæå ëè äà ìè äàäåòå ïðåäëîæåòå íÿêîå ÷åòèâî çà àëãîðèòìè÷íà ñòðàòåãèÿ Äèíàìè÷íî ïðîãðàìèðàíå, Ãðèéäè àëãîðèòúì è çà Áåêòðåêèíã. Ðåàëèçàöèÿòà äà å ñúñ cè ðåøåòêà, ÷å òîâà æèâî ìå âúëíóâà ñåãà.

    Áëàãîäàðÿ âè ïðåäâàðèòåëíî!
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	izhod.jpg‎ 
Views:	455 
Size:	42.4 KB 
ID:	25943  
    Last edited by jordan17772; 15th December 2009 at 16:31.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  11. #11
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    jordan17772?! Tè êàê ñå îïèòâàø äà ãî ïîäêàðàø? Copy/paste build è ãîòîâî?

    Èìà îïöèÿ è debug, äà ðàçáåðåø âñå ïàê êàêâî ñå ñëó÷âà. Òàêà ãëåäàéêè êîäà è ÷åòåéêè ðåä ïî ðåä äà îòêðèåø ïðîáëåìà... àêî óñïååø, òî êîìïèëàòîð òè íå "òðåáå".

    Èíà÷å èìàì ÷óâñòâîòî, ÷å ñå îïèòâàø äà ïîäêàðàø VB êîä ïîä C#. Âñå òàÿ...

    1) Èòåðàòîðèòå òðÿáâà äà èìàò è èí(de)êðåìåíò, ò.å.:
    Code:
    for (int i = 0; i <= arr.GetUpperBound(0); i++ )
    for (int j = 0; j <= arr.GetUpperBound(1); j++)
    
    for (int row = 0; row <= arr.GetUpperBound(0); row++)
    for (int col = 0; col <= arr.GetUpperBound(1); col++)
    èíà÷å ñòàâà áåçêðàåí öèêúë.

    2) Òàêà êàêòî å íàïèñàíî:
    Code:
    for (int i = 0; i <= arr.GetUpperBound(0); i++ )
    for (int j = 0; j <= arr.GetUpperBound(1); j++ )
    Console.Write(arr[row, col]);
    Console.WriteLine();
    Console.WriteLine(); - ùå ñå èçïúëíè ñëåä êðàÿ íà äâàòà öèêúëà, ò.å. âñè÷êî ùå ñå îòïå÷àòè íà åäèí ðåä. Òðÿáâà äà å:
    Code:
    for (int i = 0; i <= arr.GetUpperBound(0); i++ )
    {
    for (int j = 0; j <= arr.GetUpperBound(1); j++ )
    Console.Write(arr[row, col]);
    Console.WriteLine();
    }
    3)(ïîñëåäíî )
    êàêâà å òàçè ïðîâåðêà?!
    if (substr > "")
    Òðÿáâà äà å:
    if (!System.String.IsNullOrEmpty(substr)) èëè ïîíå
    if (substr != "")

    êàê òàêà ñòðèíã äà å ïî-ãîëÿì/ìàëúê îò ñòðèíã?! à ìîæå è ñ äúëæèíèòå ïðîñòî:
    if (substr.Length > 0)

    Òîâà å. Ðàçêîìåíòèðàé ñè:
    DispArray(larray);

    è

    // if (substr > "") Console.WriteLine("The longest comon substring is: " + substr);
    // else
    // Console.WriteLine("There is no comon substring");

    è ñè ãîòîâ.

    À è äîáàâè åäíî:
    Console.ReadLine(); â êðàÿ íà ô-öèÿ Main() òà äà ñè âèäèø ðåçóëòàòà èíà÷å ùå ñå çàòâîðè àâòîìàòè÷íî êîíçîëàòà ñëåä ïðèêëþ÷âàíå íà ñìåòêèòå.


    Åäèò: if (System.String.IsNullOrEmpty(substr)) òðÿáâà äà å ñ îòðèöàíèå äå, ò.å. ñ åäíî "!" îòïðåä èëè:

    if (!System.String.IsNullOrEmpty(substr))
    Last edited by Kaspirtov; 15th December 2009 at 21:06.
    "Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
    Äæîí Ñòþàðä Ìèë

  12. #12
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Äîáðà âå÷åð. Íàïðàâî ïî ñúùåñòâî. Çíàì êàêâî ìè êàçâàø è òèÿ ãðåøêè ãè âèæäàõ, íî íå çíàåõ êàê äà ãè îïðàâÿ...òî êîå ïî-íàïðåä â òàÿ êàøà. Õîðàòà ñ ïðåòåíöÿ äà íè íàó÷àò íà íåùî ïî, òî âñå åäíî íÿêîé âçåë äà øàðè èç VB è äà ãî îáðúùà íà C#. Íÿìà êàêâî äà ñå ÷óäèì, òîâà íå å ïúðâàòà êíèãà íà êîÿòî ïîïàäàì, êàòî ëîøà ðåàëèçàöèÿ. Ëîøîòî å ÷å íÿìà äðóãè òàêèâà çà àëãîðèòìè íà C#. Ñåäæóèê èìà õóáàâà êíèãà ïî àëãîðèòìè, íî ïðèìåðèòå òàì ñà íà äîñòà âèñîêî íèâî, à ++àëãîðèòìè íà Íàêîâ íå ìîãà äà ÿ íàìåðÿ ïî ìîéòå øèðèíè, ïúê è òúðñÿ àëãîðèòìè íà c# èëè â íàé-ëîøèÿ ñëó÷àé c++.

    Óòðå ùå ïîðàáîòÿ â íàñîêèòå, êîèòî ñè ìè äàë. Áëàãîäàðÿ ìíîãî @Kaspirtov
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  13. #13
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by jordan17772 View Post
    Áëàãîäàðÿ ìíîãî @Kaspirtov
    U r wlcome!

    Ñàìî êàòî òè ÷åòà ïîñòà äà äîáàâÿ: íå ñå õâàùàé çà åçèêà îò ïðèìåðèòå, îïèòàé ñå äà ðàçáåðåø êàêâî òðÿáâà äà ñå ñëó÷è. Ìîÿòà ïúðâà êíèæêà ñ àëãîðèòìè áåøå íà PASCAL?! åçèê, êîéòî ïîñëå íèêîãà íå ïîëçâàõ.  óíè ó÷èõ ÀDA?!

    Îáùî âçåòî, àêî çíàåø êàêâî òúðñèø ëåñíî è ùå ãî íàìåðèø êàê òî÷íî äà ñòàâà Íà êîéòî åçèê ñè ïîèñêàø.
    "Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
    Äæîí Ñòþàðä Ìèë

  14. #14
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197

    Smile

    Quote Originally Posted by Kaspirtov View Post
    U r wlcome!

    Ñàìî êàòî òè ÷åòà ïîñòà äà äîáàâÿ: íå ñå õâàùàé çà åçèêà îò ïðèìåðèòå, îïèòàé ñå äà ðàçáåðåø êàêâî òðÿáâà äà ñå ñëó÷è. Ìîÿòà ïúðâà êíèæêà ñ àëãîðèòìè áåøå íà PASCAL?! åçèê, êîéòî ïîñëå íèêîãà íå ïîëçâàõ.  óíè ó÷èõ ÀDA?!

    Îáùî âçåòî, àêî çíàåø êàêâî òúðñèø ëåñíî è ùå ãî íàìåðèø êàê òî÷íî äà ñòàâà Íà êîéòî åçèê ñè ïîèñêàø.
    È çà äà íå ïîñðàìÿ ó÷èòåëÿ ñè @Kaspirtov , ùå ïîêàæà ðåçóëòàòèòå îò íåãîâàòà ìîìîù. Íàïúëíî ðàáîòåùàòà ïðîãðàìà. Áëàãîäàðÿ íà îòçîâàëèòå ñå è òÿõíàòà ïîìîù. Áåç íåÿ íÿìàøå äà ñå ñïðàâÿ.

    Code:
    using System;
    
    class Dynamic_programming   
    {
        // òàçè ôóíêöèÿ èçâúðøâà ðàáîòàòà ïî ñúçäàâàíåòî íà äâóìåðåí ìàñèâ, êîéòî ñúõðàíÿâà ñòîéíîñòèòå
        // êîèòî îïðåäåëÿò íàé-äúëãèÿ îáù ïîäñòðèíã. 
        static void LCSubstring(string word1, string word2, string[] warr1, string[] warr2, long [,] arr) 
        {
    
            int len1, len2; // äâå ïîìîùíè öåëî÷èñëåíè ïðîìåíëèâè çà äúëæèíàòà íà íèçîâåòå
            len1 = word1.Length; // âçåìàíå äúëæèíàòà íà íèç1
            len2 = word2.Length; // âçåìàíå äúëæèíàòà íà íèç2
            for (int k = 0; k <= word1.Length - 1; k++) // òîçè öèêúë îáðúùà íèçîâåòå â ìàñèâè
            {
                warr1[k] = Convert.ToString(word1[k]);
                warr2[k] = Convert.ToString(word2[k]);
            
            }
    
            for (int i = len1 - 1; i >= 0; i--) // òóê òåçè äâà âëîæåíè for-à èçïúëíÿâàò ñðàâíåíèÿòà è ñúçäàâàò ìàñèâà
                for (int j = len2 - 1; j >= 0; j--) // çà àíàëèçà íà ñúâïàäåíèÿòà. Àíàëèçà äåéñòâà òàêà - îáõîæäà ñå
                    if (warr1[i] == warr2[j])  // äâóìåðíèÿ ìàñèâ. Ïî÷âà ñå ñ ïîñëåäíèòå åëåìåíòè (â ÷àñòíîñò áóêâè) è  
                        arr[i, j] = 1 + arr[i + 1, j + 1]; // ñå èçâúðøâàò ñðàâíåíèÿ äî êðàÿ íà äóìèòå. Ïðè îòêðèâàíå íà 
                    else // ïúðâî ñúâïàäåíèå, íà ïîçèöèÿòà â êîÿòî å, ñå ïðèñâîÿâà åäèíèöà ïëþñ ñòîéíîñòà íà ïîçöèöèÿòà 1 ðåä íàäîëó 
                        arr[i, j] = 0; // è 1 êîëîíà íà äÿñíî (ïðè ïúðâîòî ñúâïàäåíèå ùå å íóëà ñòîéíîñòà â òàçè ïîçèöèÿ). 
            // Ïðè ñëåäâàùî ñúâïàäåíèå ñëåäâàùàòà ïîçèöÿ ñå èíêðåìåíòèðà ïî ãîðåñïîìåíàòèÿ íà÷èí.
        }
    
        static string ShowString(long[,] arr, string[] wordArr) // âðúùà ñòîéíîñòòà íà íàé-äúëãèÿ îáù ïîäíèç
        {
    
            string substr = ""; // ïúðâîíà÷àëíî èíèöèàëèçèðàíå íà íèçà ñ ïðàçíèÿ íèç
    
            for (int i = 0; i <= arr.GetUpperBound(0); i++) // îáõîæäàíå äâóìåðíèÿ ìàñèâ 
                for (int j = 0; j <= arr.GetUpperBound(1);j++)
                    if (arr[i, j] > 0) // àêî îáõîäåíàòà ïîçèöèÿ å ïî-ãîëÿìà îò íóëà =>
                        substr += wordArr[j]; // èíêðåìåíòèðàíå íà íèçà ñúñ ñòîéíîñòà íà ïîçèöèÿòà â åäíîìåðíèÿ ìàñèâ íà ïúðâèÿ
            return substr;                    // íèç
        }
    
        static void DispArray(long[,] arr) { // Èçîáðàçÿâàíå íà ìàñèâà ñúçäàäåí îò LCSubstring
    
            for (int row = 0; row <= arr.GetUpperBound(0); row++)
            {
                for (int col = 0; col <= arr.GetUpperBound(1); col++)
                Console.Write(arr[row, col]);
                Console.WriteLine();
            }
        
        }
    
        static void Main(){
        
            string word1 = "raven"; // çàäàâàíå íà ñòîéíîñò íà ïúðâèÿ íèç
            string word2 = "havoc"; // çàäàâàíå íà ñòîéíîñò íà âòîðèÿ íèç
            string[] warray1 = new string[word1.Length]; // èíèöèàëèçèðàíå íà åäíîìåðåí ìàñèâ ñ ãîëåìèíà íà ïúðâèÿ íèç
            string[] warray2 = new string[word2.Length]; // èíèöèàëèçèðàíå íà åäíîìåðåí ìàñèâ ñ ãîëåìèíà íà âòîðèÿ íèç
            string substr; // ðàáîòíà ïðîìåíëèâà ñúõðàíÿâàùà íàé-äúëãèÿ îáù ïîäíèç
            long [,] larray = new long[word1.Length, word2.Length]; // ñúçäàâàíå íà äâóìåðåí ìàñèâ ñ ãîëåìèíà äúëæèíàòà íà ïúðâèÿ ïî äúëæèíàòà íà âòîðèÿ íèç
            LCSubstring(word1, word2, warray1, warray2, larray); // âèêàíå íà ôóêíöèÿòà LCSubstring îïðåäåëÿùà íàé-äúëãèÿ ïîäíèç
    
            Console.WriteLine(); // ïðàçåí ðåä
            DispArray(larray); // Èçîáðàçÿâàíå íà ìàñèâà ñúçäàäåí îò LCSubstring
    
            substr = ShowString(larray, warray1); // âçåìàíå ñòîéíîñòòà íà íàé-äúëãèÿ îáù ïîäíèç
            Console.WriteLine();
            Console.WriteLine("The strings are: " + word1 + " " + word2); // èçîáðàçÿâàíå ñòîéíîñòà íà íèç1 è íèç2
    
            if (substr != "") Console.WriteLine("The longest comon substring is: " + substr); // àêî íàé-äúëãèÿ îáù ïîäíèç
            else // å ðàçëè÷åí îò ïðàçíèÿ => äà áúäå èçîáðàçåí, â ïðîòèâåí ñëó÷àé ñúîáùåíèå çà íåñúùåñòâóâàíå íà îáù ïîäíèç
            Console.WriteLine("There is no comon substring");
            Console.ReadLine();
    
        }
    }


    È ìàëêî òåîðèÿ åñòåñòâåíî, êîÿòî å åñåíöèÿòà äî êîÿòî äîâåäå ëè÷íèÿ ìè àíàëèç.

    Dynamic programming å òåõíèêà, êîÿòî âñå ïî-÷åñòî ñå ñ÷èòà çà ïðîòèâîïîëîæíà (îáðàòíà) íà ðåêóðñèÿòà – ðåêóðñèâíîòî ðåøåíèå ñòàðòèðà îò íàé-ãîðíàòà ÷àñò è çàâúðøâà ïðîáëåìà „ñëèçàéêè íàäîëó” è ðåøàâà âñè÷êè ìàëêè çàäà÷è äî öÿëîñòíîòî íàìèðàíå íà ðåøåíèåòî çà êîÿòî å èçïîëçâàíà. Ðåøåíèåòî (ñîëþøúíà) â Dynamic programming ñòàðòèðà îò äúíîòî (íàé-äîëíèÿ êðàé), ðåøàâà ðàçáèòàòà çàäà÷à íà ìíîãî ðåøåíèÿ è ãè êîìáèíèðà â öÿëîñòíîòî ðåøåíèå (öåëòà íà çàäà÷àòà – „the big
    Problem”).
    Ðåêóðñèâíèòå ðåøåíèÿ (solutions) íà çàäà÷èòå ÷åñòî äàâàò ÷óäåñíè ðåçóëòàòè, íî íå íîñÿò íóæíàòà åôèêàñíîñò. C# êîìïèëàòîðà, êàêòî è êîìïèëàòîðèòå çà äðóãèòå åçèöè íå ìîæå äà ïðåâåäå „åëåãàíòíî” ðåêóðñèâíèÿ êîä äî ìàøèíåí, â ðåçóëòàò íà êîåòî òîé å íååôèêàñåí ïðè âñå ÷å êîìïþòúðíàòà ïðîãðàìà å åëåãàíòíà.
    Ìíîãî çàäà÷è â ïðîãðàìèðàíåòî, êîèòî èìàò ðåêóðñèâíè ðåøåíèÿ, ìîãàò äà áúäàò ïðåíàïèñàíè ÷ðåç ïîëçâàíåòî íà òåõíèêèòå íà äèíàìè÷íîòî ïðîãðàìèðàíå. Ðåøåíèåòî íà çàäà÷à îò äèíàìè÷íîòî ïðîãðàìèðàíå ñúçäàâà òàáëèöà, íàé-÷åñòî ïîëçâà ìàñèâ, êîéòî ñúäúðæà ðåçóëòàòèòå íà ðàçëè÷íèòå ïîäðåøåíèÿ (subsolutions).  êðàÿ, êîãàòî àëãîðèòúìà å çàâúðøèë, ðåøåíèåòî íà çàäà÷àòà ñå îòêðèâà â òàçè òàáëèöà.


    Çàäà÷à çà íàìèðàíå íà íàé-äúëúã îáù ïîäíèç. (Finding the Longest Common Substring)
    Çàäà÷à, êîÿòî ñå ïîääàâà íà ðåøåíèå ÷ðåç òåõíèêàòà íà äèíàìè÷íîòî ïðîãðàìèðàíå (ÄÏ) å íàìèðàíåòî íà íàé-äúëúã îáù ïîäíèç èç ìåæäó äâà íèçà. Íàïðèìåð, â äóìèòå “raven” è “havoc”, íàé-äúëãèÿ îáù ïîäíèç å “av”.
    Íåêà ïúðâî ïîãëåäíåì íàä ðåøåíèåòî íàìåðåíî ñ “ãðóáà ñèëà” (brute force solution). Äàäåíè ñà äâà íèçà À è Â. Íèå ìîæåì äà íàìåðèì íàé-äúëãèÿ îáù ïîäñòðèíã ÷ðåç ñòàðòèðàíå îò ïúðâàòà áóêâà â À è ñðàâíÿâàíå íà âñÿêà ñ áóêâà îò òåçè âúâ Â. Êîãàòî íÿìà ñúâïàäåíèå, ïðåìåñòâàìå ñå êúì ñëåäâàùàòà áóêâà â À è ñòàðòèðàíå îòíîâî ñðàâíÿâàíå ñ ïúðâàòà áóêâà îò Â, è ò.í.ò.
    Èìà ïî-äîáðî ðåøåíèå, à èìåííî ïîëçâàéêè àëãîðèòúìà íà äèíàìè÷íîòî ïðîãðàìèðàíå (ÄÏ). Àëãîðèòúìà ïîëçâà äâóìåðåí ìàñèâ çà ñúõðàíÿâàíå ðåçóëòàòà îò ñðàâíåíèÿòà íà áóêâèòå íà åäíè è ñúùè ïîçèöèè â äâàòà ñòðèíãà.  íà÷àëîòî âñåêè åëåìåíò îò ìàñèâà å èíèöèàëèçèðàí ÷ðåç íóëà “0”. Âñåêè ïúò, êîãàòî èìàìå ñúâïàäåíèå íà åäíà è ñúùà ïîçèöèÿ â äâàòà ìàñèâà, åëåìåíòà íà ñúîòâåòíàòà ðåäèöà è êîëîíà â ìàñèâà ñå èíêðåìåíòèðà ñ åäèíèöà “1”, â ïðîòèâåí ñëó÷àé åëåìåíòà ùå áúäå íóëà “0”.
    Çà äà âúçïðîèçâåäåì íàé-äúëãèÿ îáù ïîäíèç ìèíàâàìå ïðåç âñè÷êè ðåäîâå íà äâóìåðíèÿ ìàñèâ. Êîãàòî â êîëîíà ñå ñðåùíå ñòîéíîñò ïî-ãîëÿìà îò íóëà “0”, òî òÿ ùå îòãîâàðÿ íà åäíî ñúâïàäåíèå â íèçîâåòå è ùå ñúçäàäå ïîäíèç ñ êîëêîòî ñúâïàäåíèÿ íà áóêâè áúäàò îòêðèòè. Àêî íå ñå ñðåùíå ïîäíèç, âñè÷êè åëåìåíòè íà ìàñèâà ùå áúäàò íóëè “0”-ëè.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	zad1.png‎ 
Views:	417 
Size:	69.7 KB 
ID:	25977  
    Last edited by jordan17772; 16th December 2009 at 15:28.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  15. #15
    Registered User
    Join Date: Feb:2006
    Location: Plovdiv
    Posts: 392
    Ìàëêî äà îïðîñòèì êîäà è äà îïðàâèì ëîãèêàòà. Àëãîðèòúìà íàìèðà âñè÷êè ñúâïàäåíèÿ, à íå ñàìî íàé-ãîëÿìîòî è ïîñëåäñòâèÿòà îò òîâà.

    Code:
    using System;
    
    class Dynamic_programming   
    {
        // òàçè ôóíêöèÿ èçâúðøâà ðàáîòàòà ïî ñúçäàâàíåòî íà äâóìåðåí ìàñèâ, êîéòî ñúõðàíÿâà ñòîéíîñòèòå
        // êîèòî îïðåäåëÿò âñè÷êè ñúâïàäåíèÿ â òîâà ÷èñëî è íàé-äúëãèÿ îáù ïîäñòðèíã. 
        static int[,] LCSubstring(string word1, string word2) 
        {
    		var arr = new int[word1.Length + 1, word2.Length + 1];//+ 1 çà "êðàñîòà"
    		
            for (int i = word1.Length - 1; i >= 0; i--) // òóê òåçè äâà âëîæåíè for-à èçïúëíÿâàò ñðàâíåíèÿòà è ñúçäàâàò ìàñèâà
                for (int j = word2.Length - 1; j >= 0; j--) // çà àíàëèçà íà ñúâïàäåíèÿòà. Àíàëèçà äåéñòâà òàêà - îáõîæäà ñå
                    if (word1[i] == word2[j])  // äâóìåðíèÿ ìàñèâ. Ïî÷âà ñå ñ ïîñëåäíèòå åëåìåíòè (â ÷àñòíîñò áóêâè) è  
                        arr[i, j] = 1 + arr[i + 1, j + 1]; // ñå èçâúðøâàò ñðàâíåíèÿ äî êðàÿ íà äóìèòå. Ïðè îòêðèâàíå íà 
                    //else // ïúðâî ñúâïàäåíèå, íà ïîçèöèÿòà â êîÿòî å, ñå ïðèñâîÿâà åäèíèöà ïëþñ ñòîéíîñòà íà ïîçöèöèÿòà 1 ðåä íàäîëó 
                    //    arr[i, j] = 0; // è 1 êîëîíà íà äÿñíî (ïðè ïúðâîòî ñúâïàäåíèå ùå å íóëà ñòîéíîñòà â òàçè ïîçèöèÿ). 
            // Ïðè ñëåäâàùî ñúâïàäåíèå ñëåäâàùàòà ïîçèöÿ ñå èíêðåìåíòèðà ïî ãîðåñïîìåíàòèÿ íà÷èí.
    		
    		return arr;
        }
    
        static string ShowString(int[,] arr, string word) // âðúùà ñòîéíîñòòà íà íàé-äúëãèÿ îáù ïîäíèç
        {
    
    		int fromIndex = 0;
    		int lenght = 0;
    
            for (int i = 0; i <= arr.GetUpperBound(0) - 1; i++) // îáõîæäàíå äâóìåðíèÿ ìàñèâ 
                for (int j = 0; j <= arr.GetUpperBound(1) - 1; j++)
                    if (arr[i, j] > lenght) // àêî îáõîäåíàòà ïîçèöèÿ å ïî-ãîëÿìà ïîñëåäíàòà íàé-ãîëÿìà =>
    				{
    					lenght = arr[i,j];
    					fromIndex = i;
    				} // èíêðåìåíòèðàíå íà íèçà ñúñ ñòîéíîñòà íà ïîçèöèÿòà â åäíîìåðíèÿ ìàñèâ íà ïúðâèÿ
            
    		return word.Substring(fromIndex, lenght);                    // íèç
        }
    
        static void DispArray(int[,] arr) 
    	{ // Èçîáðàçÿâàíå íà ìàñèâà ñúçäàäåí îò LCSubstring
    
            for (int row = 0; row <= arr.GetUpperBound(0); row++)
            {
                for (int col = 0; col <= arr.GetUpperBound(1); col++)
                Console.Write(arr[row, col]);
                Console.WriteLine();
            }
        
        }
    
        static void Main(){
        
            string word1 = "raven123c"; // çàäàâàíå íà ñòîéíîñò íà ïúðâèÿ íèç
            string word2 = "havoc123a"; // çàäàâàíå íà ñòîéíîñò íà âòîðèÿ íèç
            string substr; // ðàáîòíà ïðîìåíëèâà ñúõðàíÿâàùà íàé-äúëãèÿ îáù ïîäíèç
            // new long[word1.Length, word2.Length]; // ñúçäàâàíå íà äâóìåðåí ìàñèâ ñ ãîëåìèíà äúëæèíàòà íà ïúðâèÿ ïî äúëæèíàòà íà âòîðèÿ íèç
            int [,] larray = LCSubstring(word1, word2); // âèêàíå íà ôóêíöèÿòà LCSubstring îïðåäåëÿùà íàé-äúëãèÿ ïîäíèç
    
            Console.WriteLine(); // ïðàçåí ðåä
            DispArray(larray); // Èçîáðàçÿâàíå íà ìàñèâà ñúçäàäåí îò LCSubstring
    		
            substr = ShowString(larray, word1); // âçåìàíå ñòîéíîñòòà íà íàé-äúëãèÿ îáù ïîäíèç
            Console.WriteLine();
            Console.WriteLine("The strings are: " + word1 + " " + word2); // èçîáðàçÿâàíå ñòîéíîñòà íà íèç1 è íèç2
    
            if (substr != "") Console.WriteLine("The longest comon substring is: " + substr); // àêî íàé-äúëãèÿ îáù ïîäíèç
            else // å ðàçëè÷åí îò ïðàçíèÿ => äà áúäå èçîáðàçåí, â ïðîòèâåí ñëó÷àé ñúîáùåíèå çà íåñúùåñòâóâàíå íà îáù ïîäíèç
            Console.WriteLine("There is no comon substring");
            Console.ReadLine();
    
        }
    }

  16. #16
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Òîçè ìåòîä íå ãî çíàåõ public string Substring(
    int startIndex,
    int length
    )

    Äîñòà êóëòóðåí áðåõ.

    Èíà÷å äà ïîïèòàì çà GetUpperBound(0) - 1 è GetUpperBound(1) - 1 êàê äà ñè ãè èáÿñíÿ. Ïî-òî÷íî ïàðàìåòúðà â ìåòîäà - 0,1,2...? Âçåìà íàé-ãîðåí èíäåêñ â ìàñèâà ëè? Èçâèíÿâàì ñå, àêî ïèòàì íåêîðåêòíî.

    P.P

    Òîçè ðåä ñúùî å ìíîãî êðàñèâ ïðèçíàâàì

    var arr = new int[word1.Length + 1, word2.Length + 1];//+ 1 çà "êðàñîòà"
    arr å äåôèíèðàí ÷ðåç ðåôåðåíöèÿ...êîéòî ãî âèêà, òîé ãî äåôèíèðà - ðàçáðàë ëè ñúì âÿðíî?
    Last edited by jordan17772; 17th December 2009 at 13:28.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  17. #17
    Registered User
    Join Date: Feb:2006
    Location: Plovdiv
    Posts: 392
    Êîãàòî äåôèíèðàìå ìàñèâà int[,] âñè÷êèòå ìó ñòîéíîñòè ñå íóëèðàò(ïîäðàçáèðàùî ñå ïîâåäåíèå íà .NET). Çà äà íå íè èçãúðìè ïðèñâîÿâàíåòî
    Code:
     arr[i, j] = 1 + arr[i + 1, j + 1];
    êîãàòî åëåìåíòà å êðàåí óâåëè÷àâàìå ðàçìåðíîñòòà íà ìàñèâà ñ ïî 1 è îò òàì ïðè òúðñåíåòî íà íàé-äúëãîòî ñúâïàäåíèå èãíîðèðàìå ïîñëåäíèòå ðàçðåäè
    Code:
        for (int i = 0; i <= arr.GetUpperBound(0) - 1; i++) 
                for (int j = 0; j <= arr.GetUpperBound(1) - 1; j++)
    Ìåæäó äðóãîòî ìîæå äà èìà íÿêîëêî ñúâïàäåíèÿ ñ åäíàêâà äúëæèíà â ñëó÷àÿò ñå âçèìà êîåòî å íà áëèçêî äî íà÷àëîòî, àêî èñêàø ñ ìàëêî óñèëèå ìîæåø äà ãî ïðîìåíèø äà âðúùà âñè÷êè íàé-äúëãè ïîäðåäåíè ïî èíäåêñà íà ñðåùàíåòî èì.

    Åäíà îò íàé ãîëåìèòå "ôèëîñîôèè" ïðè àëãîðèòìèòå å îïðåäåëÿíåòî íà êðàéíèòå(òåðìèíèðàùè) åëåìåíòè, òàêà ÷å âúòðåøíèÿ/òå öèêúë/è äà ñà ìèíèìàëíè.

  18. #18
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Å, òî ïðè âñè÷êè ïîëîæåíèÿ óâåëè÷àâàìå ðàçìåðíîñòà ñ òîÿ ðåä

    var arr = new int[word1.Length+1, word2.Length+1 ];
    Ñàìî çà êðàñîòà íå ñå ïðàâè òîâà. Êîäà å ïî-ñòàáèëåí òàêà îò ïðåäè. Èìà íåùî êîåòî ìè óáÿãâà. Áåç òîâà óãîëåìÿâàíå ïðèñâîÿâàíåòî ãúðìè IndexOutOfRangeException ïîíÿêîãà. Êîè ñà âñúùíîñò òèÿ ñëó÷àè, íå ìîãà äà ïðîóìåÿ.

    Ïðèìåðíî òàêà ãúðìè

    Code:
     string word1 = "123c321"; 
                 string word2 = "123a321";
    +
    Code:
    var arr = new int[word1.Length, word2.Length ];


    Ïðèñâîÿâàíåòè ãúðìè ìàé.
    Last edited by jordan17772; 17th December 2009 at 14:09.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  19. #19
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by jordan17772 View Post
    Áåç òîâà óãîëåìÿâàíå ïðèñâîÿâàíåòî ãúðìè IndexOutOfRangeException ïîíÿêîãà. Êîè ñà âñúùíîñò òèÿ ñëó÷àè, íå ìîãà äà ïðîóìåÿ.
    IndexOutOfRangeException e èëè êîãàòî èìàø îòðèöàòåëåí èëè êîãàòî èìàø èíäåêñ èçâúí ðàçìåðà íà ìàñèâà. Ïî ïðèíöèï èíäåêñèðàíåòî å îò íóëà íå îò åäíî. Íî ãðàíèöèòå ñà îò 1. Ò.å. íà ìàñèâ ñ 10 åëåìåíòà èìàø ìàñèâ.Ðàçìåð = 10, îáà÷å íàé-ãîëåìèÿò òè èíäåêñ å 9. Èëè ñ äðóãè äóìè, àêî íÿêúäå âèêíåø ìàñèâ[10]= íåùî_ñè ùå ãðúìíå. È òî÷íî òàêàâà ñèòóàöèÿ ïîëó÷àâàø ì/ó äðóãîòî.

    arr.GetUpperBound(íåùî_ñè), îáà÷å âðúùà íàé-ãîðíèÿ èíäåêñ, à íå ðàçìåðà. Íå çíàì çàùî ãî âèêàòå ñ -1?!
    "Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
    Äæîí Ñòþàðä Ìèë

  20. #20
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Quote Originally Posted by Kaspirtov View Post
    IndexOutOfRangeException e èëè êîãàòî èìàø îòðèöàòåëåí èëè êîãàòî èìàø èíäåêñ èçâúí ðàçìåðà íà ìàñèâà. Ïî ïðèíöèï èíäåêñèðàíåòî å îò íóëà íå îò åäíî. Íî ãðàíèöèòå ñà îò 1. Ò.å. íà ìàñèâ ñ 10 åëåìåíòà èìàø ìàñèâ.Ðàçìåð = 10, îáà÷å íàé-ãîëåìèÿò òè èíäåêñ å 9. Èëè ñ äðóãè äóìè, àêî íÿêúäå âèêíåø ìàñèâ[10]= íåùî_ñè ùå ãðúìíå. È òî÷íî òàêàâà ñèòóàöèÿ ïîëó÷àâàø ì/ó äðóãîòî.

    arr.GetUpperBound(íåùî_ñè), îáà÷å âðúùà íàé-ãîðíèÿ èíäåêñ, à íå ðàçìåðà. Íå çíàì çàùî ãî âèêàòå ñ -1?!
    Äà, ðàçáèðàì òå...òîâà ñ ìàñèâèòå å 1:1 ñúñ Ñè è ïðîáëåìè íÿìàì òóêà.

    À íà âúïðîñà òè, àìè íàëè ïúðâîíà÷àëíî óãîëåìÿâàìå äâóìåðíèÿ ìàñèâ ñ 1. Âèæ ïîñëåäíèÿ êîä. Äîñòà ïî-èç÷èñòåí å. Ìàñèâà ñ äúëæèíàòà íà íèçîâåòå +1 ãî ïðàâè âå÷å íå â Main(), à íàïðàâî ãîðå â LCSubstring. Ñ ðåôåðåíöèÿ ãî èíèöèàëèçèðà.

    Code:
    var arr = new int[word1.Length + 1, word2.Length + 1];
    Òóêà èìà íÿêàêúâ òúíúê ìîìåíò. Íå å ñàìî çà êðàñîòà è òîâà ìå ÷îâúðêà. Äàíî êîëåãàòà êàæå.

    Åòî äî òóêà ñìå ãî äîêàðàëè.
    Code:
    using System;
    
    class Dynamic_programming
    {
        // òàçè ôóíêöèÿ èçâúðøâà ðàáîòàòà ïî ñúçäàâàíåòî íà äâóìåðåí ìàñèâ, êîéòî ñúõðàíÿâà ñòîéíîñòèòå
        // êîèòî îïðåäåëÿò íàé-äúëãèÿ îáù ïîäñòðèíã. 
        static int[,] LCSubstring(string word1, string word2)
        {
            var arr = new int[word1.Length + 1, word2.Length + 1]; // ñúçäàâàìå äâóìåðåí ìàñèâ ñ äúëæèíàòà íà íèçîâåòå + 1 çà "êðàñîòà"
                                                               
            for (int i = word1.Length - 1; i >= 0; i--) // òóê òåçè äâà âëîæåíè for-à ñúçäàâàò ìàñèâà çà àíàëèçà íà ñúâïàäåíèÿòà.
                for (int j = word2.Length - 1; j >= 0; j--) //  Àíàëèçà äåéñòâà òàêà - îáõîæäà ñå äâóìåðíèÿ ìàñèâ. 
                    if (word1[i] == word2[j])  // Ïî÷âà ñå ñ ïîñëåäíèòå åëåìåíòè (â ÷àñòíîñò áóêâè) è  ñå èçâúðøâàò ñðàâíåíèÿ
                        arr[i, j] = 1 + arr[i + 1, j + 1]; // äî êðàÿ íà äóìèòå. Ïðè îòêðèâàíå íà  ïúðâî ñúâïàäåíèå, íà ïîçèöèÿòà
            // â êîÿòî å, ñå ïðèñâîÿâà åäèíèöà ïëþñ ñòîéíîñòà íà ïîçöèöèÿòà 1 ðåä íàäîëó è 1 êîëîíà íà äÿñíî 
            // Ïðè ñëåäâàùî ñúâïàäåíèå ñëåäâàùàòà ïîçèöÿ ñå èíêðåìåíòèðà ïî ãîðåñïîìåíàòèÿ íà÷èí.
    
            return arr; // âðúùà äâóìåðåí ìàñèâ
        }
    
        static string ShowString(int[,] arr, string word) // âðúùà íàé-äúëãèÿ îáù ïîäíèç
        {
            int fromIndex = 0;
            int lenght = 0;
    
            for (int i = 0; i <= arr.GetUpperBound(0) -1 ; i++) // îáõîæäàíå äâóìåðíèÿ ìàñèâ 
                for (int j = 0; j <= arr.GetUpperBound(1) -1; j++)
                    if (arr[i, j] > lenght) // àêî îáõîäåíàòà ïîçèöèÿ å ïî-ãîëÿìà ïúðâîíà÷àëíî îò íóëà
                    {
                        lenght = arr[i, j]; // ïðèñâîÿâàíå ñòîéíîñòà â òàçè ïîçèöèÿ
                        fromIndex = i; // íà÷àëíà ïîçèöèÿ îò êîÿòî ùå ïî÷íå ÷åòåíåòî
                    } 
    
            return word.Substring(fromIndex, lenght); // íàé-äúëãèÿ ïîäíèç
        }
    
        static void DispArray(int[,] arr)
        { // Èçîáðàçÿâàíå íà ìàñèâà ñúçäàäåí îò LCSubstring
    
            for (int row = 0; row <= arr.GetUpperBound(0); row++)
            {
                for (int col = 0; col <= arr.GetUpperBound(1); col++)
                    Console.Write(arr[row, col]);
                Console.WriteLine();
            }
    
        }
    
        static void Main()
        {
    
            string word1 = "raven123a"; // çàäàâàíå íà ñòîéíîñò íà ïúðâèÿ íèç
            string word2 = "havoc123a"; // çàäàâàíå íà ñòîéíîñò íà âòîðèÿ íèç
            string substr; // ðàáîòíà ïðîìåíëèâà ñúõðàíÿâàùà íàé-äúëãèÿ îáù ïîäíèç
       
            int[,] larray = LCSubstring(word1, word2); // âèêàíå íà ôóêíöèÿòà LCSubstring îïðåäåëÿùà íàé-äúëãèÿ ïîäíèç
    
            Console.WriteLine(); // ïðàçåí ðåä
            DispArray(larray); // Èçîáðàçÿâàíå íà ìàñèâà ñúçäàäåí îò LCSubstring
    
            substr = ShowString(larray, word1); // âçåìàíå ñòîéíîñòòà íà íàé-äúëãèÿ îáù ïîäíèç
            Console.WriteLine();
            Console.WriteLine("The strings are: " + word1 + " " + word2); // èçîáðàçÿâàíå ñòîéíîñòà íà íèç1 è íèç2
    
            if (substr != "") Console.WriteLine("The longest comon substring is: " + substr); // àêî íàé-äúëãèÿ îáù ïîäíèç
            else // å ðàçëè÷åí îò ïðàçíèÿ => äà áúäå èçîáðàçåí, â ïðîòèâåí ñëó÷àé ñúîáùåíèå çà íåñúùåñòâóâàíå íà îáù ïîäíèç
                Console.WriteLine("There is no comon substring");
            Console.ReadLine();
    
        }
    }
    Last edited by jordan17772; 17th December 2009 at 15:29.
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  21. #21
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by jordan17772 View Post
    Äà, ðàçáèðàì òå...òîâà ñ ìàñèâèòå å 1:1 ñúñ Ñè è ïðîáëåìè íÿìàì òóêà.

    À íà âúïðîñà òè, àìè íàëè ïúðâîíà÷àëíî óãîëåìÿâàìå äâóìåðíèÿ ìàñèâ ñ 1. Âèæ ïîñëåäíèÿ êîä. Äîñòà ïî-èç÷èñòåí å.

    Code:
    var arr = new int[word1.Length + 1, word2.Length + 1];
    Òóêà èìà íÿêàêúâ òúíúê ìîìåíò. Íå å ñàìî çà êðàñîòà è òîâà ìå ÷îâúðêà. Äàíî êîëåãàòà êàæå.
    Ìåí ìå ìúðçè äà ÷àêàì êîëåãàòà äà òè îòãîâîðè :-Ð ))))

    Åòî òóê:
    for (int i = word1.Length - 1; i >= 0; i--)
    for (int j = word2.Length - 1; j >= 0; j--)
    arr[i, j] = 1 + arr[i + 1, j + 1];

    Èòåðàòîðèòå òè èçïîëçâàò ðàçìåðà íà ñòðèíãîâåòå word1 è word2 à íå ðàçìåðèòå íà ìàñèâà arr, ïîñëå êàòî ñè äåô. ìàñèâà ñ:
    arr = new int[word1.Length, word2.Length], âìåñòî ñ +1, íà ðàâåíñòâîòî:
    arr[i, j] = 1 + arr[i + 1, j + 1];
    îùå íà ïúðâàòà èòåðàöèÿ èìàø:
    arr[word1.Length - 1, word2.Length - 1] = 1 + arr[word1.Length - 1 + 1, word1.Length - 1 + 1];

    îò êúäåòî èìàø:
    arr[word1.Length - 1, word2.Length - 1] = 1 + arr[word1.Length, word1.Length];

    Åòî òîâà:
    arr[word1.Length, word1.Length]; - å íåâúçìîæíî, ïîðàäè ïðåäíèÿ ìè ïîñò. Èñêàø åëåìåíò òî÷íî ñ ðàçìåðèòå íà ìàñèâà, êîåòî íå å èíèöèàëèçèðàíî.

    Åäèò: Íå ðàçãëåäàõ öÿëàòà ëîãèêà. Ìîæå áè å íàïèñàë çà êðàñîòà, òúé êàòî ïîñëåäíèòå åëåìåíòè òàêà è íå ñå îò÷èòàò, íî òîãàâà åòî òóê:
    for (int i = word1.Length - 1; i >= 0; i--)
    for (int j = word2.Length - 1; j >= 0; j--)
    èçïîëçâàé:
    arr.GetUpperBound() è íÿìà äà ãúðìè
    "Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
    Äæîí Ñòþàðä Ìèë

  22. #22
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Äåôàêòî arr.GetUpperBound(0) -1 è arr.GetUpperBound(1) -1 íÿìà íóæäà. Ãðåøíî å è êîëåãàòà ïî èíåðöèÿ ãî å òóðíàë.

    Îñòàâà

    Code:
     for (int i = 0; i <= arr.GetUpperBound(0); i++) // îáõîæäàíå äâóìåðíèÿ ìàñèâ 
                for (int j = 0; j <= arr.GetUpperBound(1); j++)
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

  23. #23
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by jordan17772 View Post
    Äåôàêòî arr.GetUpperBound(0) -1 è arr.GetUpperBound(1) -1 íÿìà íóæäà. Ãðåøíî å è êîëåãàòà ïî èíåðöèÿ ãî å òóðíàë.
    Çíà÷è:
    1) Òî÷íî òàì êúäåòî êîëåãàòà ãè èçïîëçâà áåðîÿòíî èìà íóæäà, òúé êàòî òîé íå ñå èíòåðåñóâà îò ïîñëåäíèÿ åëåìåíò. Èíà÷å àêî èñêàø èòåðàòîðà òè äà âçåìà è ïîñëåäíèÿ åëåìåíò â ìàñèâà, íÿìà íóæäà - äà - íÿìà äà ãðúìíå.

    2) Íàèñòèíà +1 -òàòà ñà çà êðàñîòà è áåç òÿõ àëã. âðúùà âåðåí ðåçóëòàò, íî ùå ñòàíå "ãðîçåí" êîäà, çàùîòî òðÿáâà íà ïúðâàòà èòåðàöèÿ äà èçáåãíåø "ãúðìåíåòî", ò.å. äà èìàø:

    Code:
     try
                        {
                            arr[i, j] = 1 + arr[i + 1, j + 1];
                        }
                        catch { arr[i, j] = 1; }
    èëè
    Code:
     
    if(i + 1 > arr[i, j].GetUpperBounds(0) ||
    j+1 >arr[i, j].GetUpperBounds(1))
     arr[i, j] = 1;
    else
     arr[i, j] = 1 + arr[i + 1, j + 1];
    Åäèò: Äà ïî èíåðöèÿ ãî å òóðíàë Íÿìà íóæäà îò -1.

    Åäèò2: Îòäåëíî, ÷å àêî òî÷íî ñ 1 ðàçëèêà òè òðÿáâà èçïîëçâàé ñàìî íåðàâåíñòâî, íÿìà íóæäà îò <= è ïîñëå äà âàäèø -1.

    Åäèò3: Òî.. )) Òîé ñè ãè ñëàãà -1 çàùîòî ãîðå å äåô. arr ñ +1, è ïîñëå ïðè ïðîâåðêàòà òè ãàðàíòèðàíî íÿìàø ïîäíèç íà òàçè "èçêóñòâåíà" ïîçèöèÿ. Ò.å. àêî ãîðå ñà ñ +1 äîëó íå òå èíòåðåñóâà ïîñëåäíèÿ åëåìåíò íà arr, íàèñòèíà. Òîçè ïîñëåäåí åëåìåíò è áåç òîâà ùå å íóëà è òóê:
    if (arr[i, j] > lenght)
    {
    lenght = arr[i, j];
    fromIndex = i;
    }
    Íèùî íÿìà äà ñå ïðîìåíè.
    Aìà òîâà âå÷å ñà ïîäðîáíîñòè. :-Ð
    Last edited by Kaspirtov; 17th December 2009 at 16:08.
    "Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
    Äæîí Ñòþàðä Ìèë

  24. #24
    Registered User
    Join Date: Feb:2006
    Location: Plovdiv
    Posts: 392
    çà äîïúëíèòåëíèòå êîëîíè è ðåäîâå:
    Åäíà îò íàé ãîëåìèòå "ôèëîñîôèè" ïðè àëãîðèòìèòå å îïðåäåëÿíåòî íà êðàéíèòå(òåðìèíèðàùè) åëåìåíòè, òàêà ÷å âúòðåøíèÿ/òå öèêúë/è äà ñà ìèíèìàëíè.
    Ðàçïèñàíî êàòî çà ïðåä õîðàòà:
    Code:
    #define DEBUG_SUBSTRINGS
    
    using System;
    using System.Collections.Generic;
    using System.Linq;
    
    namespace DinamicPrograming
    {
        public class StringEx
        {
            public int FromIndex { get; set; }
            public string String { get; set; }
        }
    
        public static class Extensions
        {
            public static List<StringEx> Substrings(this string word1, string word2)
            {
                var arr = new int[word1.Length + 2, word2.Length + 2];
    
                for (int i = word1.Length; i > 0; i--)
                    for (int j = word2.Length; j > 0; j--)
                        if (word1[i - 1] == word2[j - 1])
                            arr[i, j] = 1 + arr[i + 1, j + 1];
    
                var results = new List<StringEx>(word1.Length);
    
    #if DEBUG_SUBSTRINGS
    
                Console.WriteLine();
    
                for (int i = 1; i <= word1.Length; i++)
                {
                    for (int j = 1; j <= word2.Length; j++)
                        Console.Write(" {0} ", arr[i, j]);
    
                    Console.WriteLine();
                }
    
                Console.WriteLine();
    #endif
    
                for (int i = 1; i <= word1.Length; i++)
                    for (int j = 1; j <= word2.Length; j++)
                        if (arr[i, j] != 0 && arr[i - 1, j - 1] == 0)
                            results.Add(new StringEx { String = word1.Substring(i - 1, arr[i, j]), FromIndex = i - 1 });
    #if DEBUG_SUBSTRINGS
    
                foreach (var stringEx in results)
                    Console.WriteLine("start index: {0}  substring: {1}", stringEx.FromIndex, stringEx.String);
    
                Console.WriteLine();
    #endif
    
                return results.OrderByDescending(p => p.String.Length).ToList();
            }
        }
    
        class Program
        {
            static void Main(string[] args)
            {
                var word1 = "ASDrav123c";
                var word2 = "ASDhavoc123a";
    
                Console.WriteLine("The strings are: {0}  {1}", word1, word2);
    
                var result = word1.Substrings(word2);
    
                if (result.Count > 0)
                {
                    Console.WriteLine("The longest comon substrings is: ");
                    foreach (var stringEx in result.TakeWhile(p => p.String.Length == result[0].String.Length))
                        Console.WriteLine("start index: {0}  substring: {1}", stringEx.FromIndex, stringEx.String);
    
                }
                else
                    Console.WriteLine("There is no comon substring");
                Console.ReadLine();
            }
        }
    }
    Àêî íåùî íå òè å ÿñíî ïèòàé, íî ïúðâî ðàçãëåäàé äîáðå êîäà è ãî ïóñíè ïðåç äåáúãåðà çà äà âèäèø êàêâî ñå ñëó÷âà.
    Last edited by JanBird; 17th December 2009 at 16:41. Reason: ãðåøêà â êîäà

  25. #25
    read-only jordan17772's Avatar
    Join Date: May:2008
    Location: Âåëèêî Òúðíîâî
    Posts: 3,197
    Îò ãëåäíà òî÷êà íà åôåêòèâíîñò, ïî-äîáðå äà ñå ïðàâÿò ïðîâåðêèòå â ïî-ìàëêèÿ ìàñèâ. È òîâà íàìàëÿíå ñ åäèíèöà ñïåñòÿâà âðåìå. Òîâà å ïîäðîáíîñò. Ðàçáðàõ êúäå ãúðìè êîäà ïðåäè. Ïðîñòî èñêàìå äà äîáàâèì íåùî, çà êîåòî äàâàìå èíäåêñ èçâúí îáñåãà íà äåôèíèðàíèÿ âå÷å ìàñèâ. ßñíî.

    È òóêà:

    if (arr[i, j] > lenght)
    {
    lenght = arr[i, j];
    fromIndex = i;
    }
    lenght ïîñòúïêîâî êîãàòî ñòàíå ñ íàé-ãîëÿìàòà ñè ñòîéíîñò. Ïðèìåðíî èìàìå 4 ñúâïàäåíèÿ è ùå ñå ïîìíè äî òàçè ñòîéíîñò. Ãàðàíòèðàíî òî÷íî ïîäíèçà ñ ãîëåìèíàòà ìó ùå å íàé-ãîëÿìèÿ. Ìíîãî õèòðî ðåøåíèå (ñ òúíêè ìîìåíòè )ñå î÷åðòà .
    AMD Phenom II X4 980 Black @4GHz with 1.425v |GA-MA790FX-UD5P| Prolimatech Megahalems + Noctua NF-S12B-FLX |EVGA GeForce GTX 1060 SSC 6GB ACX 3.0 | 4Õ2GB G.Skill F2-8000CL5D-4GBPQ | 1TB + 640GB WD Black | Seasonic X750 Gold | CM 690 II Advanced Black | Logitech Wave Pro | Edifier R1850DB

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Copyright © 1999-2011 Õàðäóåð ÁÃ. Âúçìîæíî å ñúäúðæàíèåòî íà òàçè ñòðàíèöà äà å îáåêò íà àâòîðñêè ïðàâà.
iskamPC.com | mobility.BG | Bloody's Techblog | Êðèïòîâàëóòè è ìàéíèíã | 3D Vision Blog | Ìàãàçèí çà åëåêòðîííè öèãàðè