Loading...
danila.vanila.3 avatar danila.vanila.3 9 Точки

Помощ със задача на 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;

Тагове:
1
Общи приказки
RoYaL avatar RoYaL Trainer 6849 Точки

/Offtopic:

Условието в модерен вариант:

- Ако 18 годишно момче може да набере в гората 4 кг боровинки за 1 час, и ако 16 годишно момиче може да набере в гората 5 кг боровинки за 2 часа, то едва ли двамата заедно в гората за 2 часа могат да наберат 13 кила боровинки...

Endoff/ :D

Тая задачка нещо не е така... като започваш на позиция 0,0 не трябва ли да събереш боровинките и от там.

И другото което е с тоя цикъл - така май си се движиш на зиг заг, не че съм го пробвал, ама трябва да избереш единия от двата хода - този с повечето боровинки, а ти предприемаш и двата, така?

И третото - какво ако имаме следната матричка:

5 6

6 8

[0,0] = 5. Тръгваш от там. Надясно ли, надолу ли ще тръгнеш? Все е 6?

Иначе ми се вижда като задачка с решение с while(). Имаш си Х и У координати, циклиш докато не стигнеш долу в дясно (условието на while-a). Като се преместиш надясно - увеличаваш У-а, като се преместиш надолу - увеличаваш Х-а.

1
danila.vanila.3 avatar danila.vanila.3 9 Точки

Благодаря за забележките, ще помисля още и мисля че ще успея да се справя с тези насоки. :)

Само едно въпросче- преди да влезем във for-а присвояваме стойността на нулевия елемент на MaxBorovinki . След това добавяме към тази стойност и тази на съответно по-големия елемент (в тази част вероятно имам грешки). Така не се ли брои и нулевия елемент?

Ако бъркам моля кажете какво имате в предвид за да не повтарям същата грешка. :)

А по въпроса в движението при всички положения човечето се движи или на зиг-заг или в права линия защото няма право да се движи подиагонал. 

0
RoYaL avatar RoYaL Trainer 6849 Точки

Въпросът ми беше дали човечето ще се премести там където са повечето боровинки т.е. при матрица

1 2 3 4

1 1 5 2

Трябва да направи първо 2 хода на дясно, докато стигне [3] После един надолу и един неизбежно надясно, защото няма надолу.

Нали така?

Тогава би изглеждало нещо такова (не гарантирам за вярност на синтаксиса):

int x = 0;

int y = 0;

int blueberries = pole[0][0]

while (x < sizeof(pole)  && y < sizeof(pole[x])) {

    if (pole[x][y+1] > pole[x+1][y]) {

        blueberiies += pole[x][y+1];

        y++;

    } else {

       blueberiies += pole[x+1][y];       

       x++;

   }

}

 

Като може би ще ти трябват две допълнителни условия в while-а. Ако си стигнала до най-дясно, да не прави проверки, а да слиза само надолу. Ако си стигнала до най-долу, да не прави проверки а да се движи само надясно.

Има лийк в този код и това е, както посочих по-рано, ако и дясната и долната позиция са еднакви. Тогава ще влезе в else-а, т.е. ще тръгне надолу.

P.S.: Не бях видял, че инициализираш боровинките с pole[0][0]. Видях само int MaxBorovinki. Да, права си, брои се.

1
20/01/2015 15:31:59
Filkolev avatar Filkolev 4482 Точки

По този начин обхождаш масива по определена схема - вървиш надолу или надясно единствено в зависимост от стойностите на съседните клетки. На теб обаче ти трябва алгоритъм, който да обходи всички възможни пътища и да намери този с най-голяма тежест.  

Мисля, че ти трябва нещо от рода на Depth-First Search. Все още в СофтУни не сме провеждали курс по Алгоритми, може да погледнеш лекциите на Телерик тук, имат и решени задачи от подобно естество. 

3
mihayloff14 avatar mihayloff14 824 Точки

Аз мисля, че по-удачен вариант е Breadth-First Search, тъй като той обхожда в широчина.

Depth-First е подходящ, когато търсиш най-кратък път, но в случая търсим пътя, при който вземаме максимално много боровинки.

Ето и една задача, която съм направил използвайки споменатия алгоритъм:

URL

Мисля че ако се преработи отчасти метода за обхождане, ще може да се реши задачата. Общо взето трябва да се премахнат вариантите, в които обхожда масива нагоре и наляво, защото не ни е позволено да го обхождаме по този начин.

Освен това, допускайки че всички полета са пълни с боровинки, тогава не е нужна проверка за това дали сме стъпили на боровинка. Това обуславяно и от факта, че се движим само надолу и надясно, което значи, че няма начин да попаднем на вече обходен маршрут.

2
20/01/2015 15:47:21
danila.vanila.3 avatar danila.vanila.3 9 Точки

Благодаря за готовността да помогнете. Ще разгледам материалите за алгоритмите които предлагате но не съм убедена че ще мога да ги използвам защото не съм учила графи или класове. :0

0
RoYaL avatar RoYaL Trainer 6849 Точки

Трябва ти само BreadthFirstSearch() метода, който го има в примера, от който даже може да разкараш малко код - като този който има row-1 и col-1.

0
danila.vanila.3 avatar danila.vanila.3 9 Точки

RoYaL благодаря за полезното инфо.. Прав си, трябва да се добави и условие за еднаквост на 2те клетки както сам каза ако напр. имаме

1 3 7

3 5 9

6 2 0

в този случай се очаква да върви 1 - 3 - 7 - 9 -0 т.е 20 боровинки

а иначе за въпроса дали да е for или while няма ли и двата цикъла да обходят всички елементи?

 

 

0
RoYaL avatar RoYaL Trainer 6849 Точки

while-а в случая ще обходи само там, на където инкрементираш. Т.е. Х-а или У-ка. В твоя случай с for-a ще направи абсолютно цялото обхождане. До краяно дясно на всеки ред и до крайно долу на всяка колона.

Остава все пак въпросът дали трябва да се предвиди някакво AI. Т.е. дори и следващата боровинка да е по-малка, то ако по-следващата е супер голямо число, все пак да отиде нататък, за да я събере.

Това както колегата по-горе е споменал се извършва с един от известните алгоритми за обхождане на графи. В случая е breadth-first.

1
20/01/2015 15:43:47
danila.vanila.3 avatar danila.vanila.3 9 Точки

Да прав си. Благодаря. А иначе ако има условие което да проверява както каза напр. ако матрицата е 

1 3 0

1 3 1

9 2 7

да провери евентуално пътищата 

1 -3 -2 -7 т.е 12 боровинки както би направило ако проверява само съседните числа или

1 -1 -9 -2 -7 т.е. 20 боровинки

Прав си не се бях замислила за тази възможност. Ако се сравняват сборовете на съседните 2 по-големи числа дали ще стане? 

Например ако използваме същата матрица

1+(1+9) или 1+ (3+3)

Ако се направи така ще бъде ли достатъчно обективно или пак ще се изпускат решения?

0
RoYaL avatar RoYaL Trainer 6849 Точки

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

 

Нямаш шанс. Първо ще сравняш съседните две. При тази схема по-горе ще решиш да сравняваш съседните 3? Пет? :) Дали ще се опиташ да колектнеш първо 1000 и после 605 или ще се опиташ да вземеш 501, 500 и 605? По между 1000 и 605 има пък 27, което е повече от 18 + 1 + 2+ 3 които се намират на между 500 и 605.

Ще трябва или да притеглиш всички възможни маршрути както каза Фил, или някакъв друг тип предикшън и метод на елиминацията. Може да пробваш да измислиш и нещо свое, Аз бих се пробвал да тегля маршрутите само които си струват - в случая само тези двата. Ако има такива фрапантни разлики в числата, може да се намерят с някакви екстракт функции. За С++ не съм сигурен, но останалите съвременни езици имат функции за намиране на най-голямо число в масив. The choices are endless :)

 

0
g.stoyanov avatar g.stoyanov 776 Точки

Ето едно решение с рекурсия написано на C#: Max Path In Matrix

Обхождат се всички възможни пътища чрез двете посоки и най накрая се сравняват за да се вземе кой е със максимална сума.

Ако имаш въпроси питай!

0
danila.vanila.3 avatar danila.vanila.3 9 Точки

Благодаря, мисля че това ще свърши доста добра работа. :)

 

0
g.stoyanov avatar g.stoyanov 776 Точки

Надявам се че не е била целта да ти решим задачата ;)

Сега седни осмисли нещата, опитай се да вникнеш в решението, след което седни и я пренапиши на С++.

0
RoYaL avatar RoYaL Trainer 6849 Точки

Еее, уби интригата, хаха. Май не смята последния елемент иначе?

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.