Results 1 to 25 of 67
Thread: Chars property â C#
Hybrid View
-
15th December 2009 14:20 #1
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
-
15th December 2009 14:54 #2
Çà òóé ëè ïèòàø?
http://msdn.microsoft.com/en-us/libr...ing.chars.aspxÏîñëåäíà ðåäàêöèÿ: èçâúðøåíà îò XaMaB; íà äíåøíà äàòà. 0.42 ñåêóíäè ñëåä ïóñêàíå íà ïîñòà
In God we Trust (all others must submit a X.509 certificate). Àêî ñïîðèø ñ èäèîò, âåðîÿòíî è òîé ïðàâè ñúùîòî èëè ñè ïîïàäíàë íà ïàðòèåí (íåïúëåí) ÷ëåí
-
15th December 2009 15:06 #3
Òúêìî ñè âúâåæäàì ïðèìåðà â òåìàòà äèíàìè÷íî ïðîãðàìèðàíå, çà íàìèðàíå íàé-ãîëÿì ïîäíèç ìåæäó íÿêîëêî. È õîï, ïèøà ñâîéñòâîòî 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
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
-
15th December 2009 15:41 #4
 ëèíêà ïî-ãîðå òî÷íî ñè å îïèñàíî ÷å òîâà ïðîïúðòè ãî èìàø ñàìî âúâ VB.
çà Ö-ðåøåòêà òè å warr1[k] = word1[k]Ïîñëåäíà ðåäàêöèÿ: èçâúðøåíà îò XaMaB; íà äíåøíà äàòà. 0.42 ñåêóíäè ñëåä ïóñêàíå íà ïîñòà
In God we Trust (all others must submit a X.509 certificate). Àêî ñïîðèø ñ èäèîò, âåðîÿòíî è òîé ïðàâè ñúùîòî èëè ñè ïîïàäíàë íà ïàðòèåí (íåïúëåí) ÷ëåí
-
15th December 2009 15:43 #5
È àç íå îòêðèâàì òàêúâ ìåòîä.
Ïðîñòî çàìåíè òîâà:
ñ òîâà:Code:warr1[k] = word1.Chars(k);
EDIT:Code:warr1[k] = word1[k];
-
15th December 2009 15:49 #6
Ìåðñè, ñåãà èçëèçà 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
-
15th December 2009 15:56 #7Code:
warr1[k] = word1[k].ToString();
-
15th December 2009 16:00 #8
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
-
15th December 2009 16:04 #9
-
15th December 2009 16:21 #10
Åé ãî öåëèÿ êîä, àêî íÿêîé ìîæå äà ãî ïîäêàðà, åâàëà. Ïðîñòî ïîäèãðàâêà ñ òèÿ ïðèìåðè â òàçè Âåëèêà òâîðáà íà Êåìáðè÷ ÞíèâúðñèòÈ Ïðåññ
Òîâà òðÿáâà äà èçêàðâà[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è ðåøåòêà, ÷å òîâà æèâî ìå âúëíóâà ñåãà.
Áëàãîäàðÿ âè ïðåäâàðèòåëíî!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
-
15th December 2009 20:55 #11
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) Òàêà êàêòî å íàïèñàíî:
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)(ïîñëåäíî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(); }
)
êàêâà å òàçè ïðîâåðêà?!Òðÿáâà äà å: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.
"Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
Äæîí Ñòþàðä Ìèë
-
15th December 2009 21:40 #12
Äîáðà âå÷åð. Íàïðàâî ïî ñúùåñòâî. Çíàì êàêâî ìè êàçâàø è òèÿ ãðåøêè ãè âèæäàõ, íî íå çíàåõ êàê äà ãè îïðàâÿ...òî êîå ïî-íàïðåä â òàÿ êàøà. Õîðàòà ñ ïðåòåíöÿ äà íè íàó÷àò íà íåùî ïî, òî âñå åäíî íÿêîé âçåë äà øàðè èç 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
-
15th December 2009 21:49 #13
U r wlcome!

Ñàìî êàòî òè ÷åòà ïîñòà äà äîáàâÿ: íå ñå õâàùàé çà åçèêà îò ïðèìåðèòå, îïèòàé ñå äà ðàçáåðåø êàêâî òðÿáâà äà ñå ñëó÷è. Ìîÿòà ïúðâà êíèæêà ñ àëãîðèòìè áåøå íà PASCAL?! åçèê, êîéòî ïîñëå íèêîãà íå ïîëçâàõ.  óíè ó÷èõ ÀDA?!
Îáùî âçåòî, àêî çíàåø êàêâî òúðñèø ëåñíî è ùå ãî íàìåðèø êàê òî÷íî äà ñòàâà
Íà êîéòî åçèê ñè ïîèñêàø.
"Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
Äæîí Ñòþàðä Ìèë
-
16th December 2009 15:20 #14
È çà äà íå ïîñðàìÿ ó÷èòåëÿ ñè @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”-ëè.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
-
16th December 2009 20:47 #15Registered 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(); } }
-
17th December 2009 12:59 #16
Òîçè ìåòîä íå ãî çíàåõ public string Substring(
int startIndex,
int length
)
Äîñòà êóëòóðåí áðåõ.
Èíà÷å äà ïîïèòàì çà GetUpperBound(0) - 1 è GetUpperBound(1) - 1 êàê äà ñè ãè èáÿñíÿ. Ïî-òî÷íî ïàðàìåòúðà â ìåòîäà - 0,1,2...? Âçåìà íàé-ãîðåí èíäåêñ â ìàñèâà ëè? Èçâèíÿâàì ñå, àêî ïèòàì íåêîðåêòíî.
P.P
Òîçè ðåä ñúùî å ìíîãî êðàñèâ ïðèçíàâàì
arr å äåôèíèðàí ÷ðåç ðåôåðåíöèÿ...êîéòî ãî âèêà, òîé ãî äåôèíèðà - ðàçáðàë ëè ñúì âÿðíî?var arr = new int[word1.Length + 1, word2.Length + 1];//+ 1 çà "êðàñîòà"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
-
17th December 2009 13:27 #17Registered User
Join Date: Feb:2006
Location: Plovdiv
Posts: 392
Êîãàòî äåôèíèðàìå ìàñèâà int[,] âñè÷êèòå ìó ñòîéíîñòè ñå íóëèðàò(ïîäðàçáèðàùî ñå ïîâåäåíèå íà .NET). Çà äà íå íè èçãúðìè ïðèñâîÿâàíåòî
êîãàòî åëåìåíòà å êðàåí óâåëè÷àâàìå ðàçìåðíîñòòà íà ìàñèâà ñ ïî 1 è îò òàì ïðè òúðñåíåòî íà íàé-äúëãîòî ñúâïàäåíèå èãíîðèðàìå ïîñëåäíèòå ðàçðåäèCode:arr[i, j] = 1 + arr[i + 1, j + 1];
Ìåæäó äðóãîòî ìîæå äà èìà íÿêîëêî ñúâïàäåíèÿ ñ åäíàêâà äúëæèíà â ñëó÷àÿò ñå âçèìà êîåòî å íà áëèçêî äî íà÷àëîòî, àêî èñêàø ñ ìàëêî óñèëèå ìîæåø äà ãî ïðîìåíèø äà âðúùà âñè÷êè íàé-äúëãè ïîäðåäåíè ïî èíäåêñà íà ñðåùàíåòî èì.Code:for (int i = 0; i <= arr.GetUpperBound(0) - 1; i++) for (int j = 0; j <= arr.GetUpperBound(1) - 1; j++)
Åäíà îò íàé ãîëåìèòå "ôèëîñîôèè" ïðè àëãîðèòìèòå å îïðåäåëÿíåòî íà êðàéíèòå(òåðìèíèðàùè) åëåìåíòè, òàêà ÷å âúòðåøíèÿ/òå öèêúë/è äà ñà ìèíèìàëíè.
-
17th December 2009 13:56 #18
Å, òî ïðè âñè÷êè ïîëîæåíèÿ óâåëè÷àâàìå ðàçìåðíîñòà ñ òîÿ ðåä
Ñàìî çà êðàñîòà íå ñå ïðàâè òîâà. Êîäà å ïî-ñòàáèëåí òàêà îò ïðåäè. Èìà íåùî êîåòî ìè óáÿãâà. Áåç òîâà óãîëåìÿâàíå ïðèñâîÿâàíåòî ãúðìè IndexOutOfRangeException ïîíÿêîãà. Êîè ñà âñúùíîñò òèÿ ñëó÷àè, íå ìîãà äà ïðîóìåÿ.var arr = new int[word1.Length+1, word2.Length+1 ];
Ïðèìåðíî òàêà ãúðìè
+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
-
17th December 2009 15:14 #19
IndexOutOfRangeException e èëè êîãàòî èìàø îòðèöàòåëåí èëè êîãàòî èìàø èíäåêñ èçâúí ðàçìåðà íà ìàñèâà. Ïî ïðèíöèï èíäåêñèðàíåòî å îò íóëà íå îò åäíî. Íî ãðàíèöèòå ñà îò 1. Ò.å. íà ìàñèâ ñ 10 åëåìåíòà èìàø ìàñèâ.Ðàçìåð = 10, îáà÷å íàé-ãîëåìèÿò òè èíäåêñ å 9. Èëè ñ äðóãè äóìè, àêî íÿêúäå âèêíåø ìàñèâ[10]= íåùî_ñè ùå ãðúìíå. È òî÷íî òàêàâà ñèòóàöèÿ ïîëó÷àâàø ì/ó äðóãîòî.
arr.GetUpperBound(íåùî_ñè), îáà÷å âðúùà íàé-ãîðíèÿ èíäåêñ, à íå ðàçìåðà. Íå çíàì çàùî ãî âèêàòå ñ -1?!
"Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
Äæîí Ñòþàðä Ìèë
-
17th December 2009 15:19 #20
Äà, ðàçáèðàì òå...òîâà ñ ìàñèâèòå å 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
-
17th December 2009 15:28 #21
Ìåí ìå ìúðçè äà ÷àêàì êîëåãàòà äà òè îòãîâîðè :-Ð
))))
Åòî òóê:
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() è íÿìà äà ãúðìè"Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
Äæîí Ñòþàðä Ìèë
-
17th December 2009 15:42 #22
Äåôàêòî 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
-
17th December 2009 15:48 #23
Çíà÷è:
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.
"Íèêîãà íå ìîæåì äà ñìå ñèãóðíè, ÷å ìíåíèåòî, êîåòî ñå ñòðåìèì äà çàäóøèì å ïîãðåøíî, à è äà áÿõìå ñèãóðíè, ïàê áè áèëî ïîãðåøíî äà ãî çàäóøèì."
Äæîí Ñòþàðä Ìèë
-
17th December 2009 16:21 #24Registered 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: ãðåøêà â êîäà
-
17th December 2009 16:26 #25
Îò ãëåäíà òî÷êà íà åôåêòèâíîñò, ïî-äîáðå äà ñå ïðàâÿò ïðîâåðêèòå â ïî-ìàëêèÿ ìàñèâ. È òîâà íàìàëÿíå ñ åäèíèöà ñïåñòÿâà âðåìå. Òîâà å ïîäðîáíîñò. Ðàçáðàõ êúäå ãúðìè êîäà ïðåäè. Ïðîñòî èñêàìå äà äîáàâèì íåùî, çà êîåòî äàâàìå èíäåêñ èçâúí îáñåãà íà äåôèíèðàíèÿ âå÷å ìàñèâ. ßñíî.
È òóêà:
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




Reply With Quote

Lenovo ThinkPad 15 èëè IdeaPad 15
5th May 2023, 22:16 in Ìîáèëíè êîìïþòðè