656

Основы - нужны или нет?

всё-таки нужны ли основы?кто-то называет это математикой, но до математике этому далеко.нужно ли, если и так компилируются программы, работают, радуя глаз, ведь всё равно непонятно как работает. нужнозадача про острова. Зоро и Кернел дали свои (почти идентичные решения), идея состоит примерно в этом:проходим весь массив, находим остров, рекурсивно помечаем все граничащие с ним точки.это решение. это работающее решение. назовём его первым, (1)но (2)for (i=0;i1)a[i,j]=a[i-1,j];else if (a[i,j-1]>1)a[i,j]=a[i,j-1];elsea[i,j]=++count;тоже решениея не проверял обращение в несуществующим элементам массива, не считаю площадь максимальную, тк я показываю только алгоритм (кто хочет может самостоятельно сделать).разница? сравнивать надо?во втором максимальное количество проверок = 3*m*nв первом = 5*m*nпочти в два раза. плюс в первом рекурсия, что очень сильно уменьшает скорость работы программа (Кернел должен понять меня, раз он близко знаком с асмом).так же я бы хотел расмотреть более известную вам всем задачу и тоже вариант оптимизации, на данной задаче оптимизация существеннее. задача носит название Лабиринт, алгоритм - волновой.у нас есть массив, в котором 1 означают непроходимые участки, 0 проходимые. есть две координаты х(xs,ys) у(xe,ye) координаты соответственно начальной и конечной точек. надо найти кратчайший (кратчайшие - это не обязательно условие, но задача становится интереснее) путь от начальной до конечной точки.алгоритмпример лабиринта11111111111х000000011111110101100000000110000000y11111111111надо попасть из х в у. count=2точку х помечаем как 2соседние точки с 2 помечаем как 3соседние точки с 3 помечаем как 4или тд пока не дойдём до конечной точки. это называется первая часть алгоритма.1111111111123456789111111181a11000009ab11000000bc11111111111вот мы и дошли точку.сам путь находится просто зная "номер" точки, куда надо попать ( внашем случае "с") находим, стоящую рядом с номером на еденицу меньше и так, пока не дойдём до двойки - вторая часть алгоритма.представьте себе чистую поверхность воды, вы бросаете камешек, круглые волны от места попадания камешка расходятся по сторонам. примерно так и работает данный алгоритм, откуда и название(кто дочитал до этого места, но всё равно уверен, что это всё математика никому не нужная, я напомню, что лабиринт - частный случай для этого алгоритма, общий случай - граф, и алгоритм можно применять даже для проэктирования запросов к базе данных, уже много об этом писалось, поищите в гугле "применение графов")решение, который нам всем показывали:a[xs,ys] = 2;count = 2;while(1){for (i=0;i
0