Помощ със задача на C++
Здравейте, имам нужда от помощ да си намеря грешка в задача на C++. Условието е: Дефинираме Двумерен статичен масив. [m][n] от цели числа (тип int).Масива представлява поле и във всяка клетка има толкова боровинки колкото е голямо числото в нея. Човече тръгва от горния ляв ъгъл([0][0]) и се движи САМО надясно и надолу. Колко е максималният брой боровинки, който човечето може да събере докато стигне до клетка [m][n].
Може да бъде решена и със указатели, динамични обекти, цикли така че ако някой има идеи за решение с някое от тях моля да сподели.
ето го моят код. Масивът и максималният брой колони и редове са инициализирани, но както всички знаем има ограничение за дължината на кода затова качвам останалата част от него:
int MaxBorovinki;
MaxBorovinki=Pole[0][0];
for (i= 0; i<n; i++)
{
for(j=0; j<m; j++)
{
if ((Pole[i][j+1])>(Pole[i+1][j]))
MaxBorovinki+=Pole[i][j+1];
else
MaxBorovinki+=Pole[i+1][j];
}
}
cout<<MaxBorovinki;
Аз мисля, че по-удачен вариант е Breadth-First Search, тъй като той обхожда в широчина.
Depth-First е подходящ, когато търсиш най-кратък път, но в случая търсим пътя, при който вземаме максимално много боровинки.
Ето и една задача, която съм направил използвайки споменатия алгоритъм:
URL
Мисля че ако се преработи отчасти метода за обхождане, ще може да се реши задачата. Общо взето трябва да се премахнат вариантите, в които обхожда масива нагоре и наляво, защото не ни е позволено да го обхождаме по този начин.
Освен това, допускайки че всички полета са пълни с боровинки, тогава не е нужна проверка за това дали сме стъпили на боровинка. Това обуславяно и от факта, че се движим само надолу и надясно, което значи, че няма начин да попаднем на вече обходен маршрут.
Благодаря за готовността да помогнете. Ще разгледам материалите за алгоритмите които предлагате но не съм убедена че ще мога да ги използвам защото не съм учила графи или класове. :0
Трябва ти само BreadthFirstSearch() метода, който го има в примера, от който даже може да разкараш малко код - като този който има row-1 и col-1.
Аз го предложих от гледна точка на това, че трябва да вземем целия път и да му сметнем теглото. Т.е. трябва да стигнем до края, да запазим теглото (броя боровинки), след това да сметнем теглото на друг път, отново цял и т.н., запазвайки най-голямото тегло. На мен ми се струва, че това е точно обхождане в дълбочина.
Breadth-First е по-скоро с идеята да стигнеш до някъде и да спреш, докато тук искаме да стигнем до края, да се върнем, да стигнем пак до края и т.н.
Задачата сигурно е сравнително лесна; надявам се курсът по алгоритми да е по-скоро, защото материята е доста интересна и полезна.
Пфф, голяма заигравка е тая задачка, а трябва и да работя :D А се заиграх да я правя :D
Всъщност сега като се замисля, максималният брой малинки, които могат да се съберат не е ли параметър, който просто зависи от броя редове и колони на двумерния масив?
Ако двумерния масив е всъщност матрица, тогава по какъвто и път да се поеме с възможностите за обхождане само надясно и надолу, тогава максималния брой боровинки, които могат да се съберат не е ли - сбора от колоните и редовете - 1?
А ако не е матрица, тъй като трябва да стигнем най-долу в дясно, тогава броя би бил:
сбора на редовете + колоните на последния ред - 1
Не разбирам какво искаш да кажеш. На прима виста си измислих някаква матричка, не съм я екзаминвал много, само леко се позамислих над максималния брой
1 2 3 4 5 1000 6 7
15 16 501 18 8 20 27 40
50 80 4 500 1 2 3 4
60 120 30 8 3 4 605 8
4 реда и 8 колони. Как може да се пресметне максималния брой?
По мои сметки имаш няколко възможности
1+2+3+4+5+1000+20+27+3+605+8 = 1678
1+15+16+501+18+500+8+3+4+605+8 = 1679
Останалите са драстично по-малко
Ахаа, явно грешно съм разбрал (или прочел) условието. Реших, че всички полета от матрицата съдържат по една боровинка, което ме доведе до предната ми мисъл.
Да, в такъв случай ще трябва да се използва нещо по-смислено от това, което предложих. :D
Всъщност какво ни е дадено - конкретна матрица със стойности, или само размерите й? Ако е второто, Преслав е прав, просто намираме колко клетки има между началната и крайната и умножаваме по максималната стойност на int-a. Ако е първото - трябва да се търси някаква рекурсия, която да обходи вариантите и да намери този, който се търси.
Имаме матрица със максимум [m][n] като конкретните стойности се инициализират от клавиятура т.е. като се отвори черното екранче се вувежда реалния брой колони и редици и след това те чака да подадеш и стойности за всяка клетка.