| Вопрос: Помогите кто-нибудь! Хитрая задачка! | Добавлено: 16.10.06 15:42 |
Автор вопроса:  virus
|
|
Друг предложил мне написать код под одну программу. Смысл ее таков:
"Получил я вчера задание нарисовать картинку размером H на W пикселей, обертку для конфет "Сосиска в шоколаде". Творчество – процесс тонкий, вдохновение требуется. А тут – как топором отрубило, ничего не выходит… От безысходности я нарисовал на белом экране красную замкнутую линию, толщиной в один пиксель. Сколько пикселей оказалось в области, ограниченной красной линией?" Ограничения: 1<H,W<=100 Каждый красный пиксель имеет общие стороны ровно с двумя красными пикселями. Ввод/вывод: Программа должна прочитать с клавиатуры: с первой строки – два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый – нулем. Программа должна вывести на экран результат - число пикселей, ограниченных линией. Пример: Ввод> 5 7 Ввод> 0 0 0 1 1 1 0 Ввод> 0 1 1 1 0 1 0 Ввод> 0 1 0 0 0 1 0 Ввод> 0 1 1 1 1 1 0 Ввод> 0 0 0 0 0 0 0 Вывод> 4 Вообще данная задача должна решаться на Паскале, но т.к. я не особо умею с ним работать, то решил сделать ее на VB. Мне эта задача не нужна, но когда я столкнулся с ней и не смог решить ее, это стало делом принципа. Если найдется добрый человек - пусть пишет на мыло: dimon.fox@list.ru |
| Ответы | Всего ответов: 14 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 16.10.06 16:43 |
| Увеличиваешь поле с каждой стороны на 1 пиксель, заливаешь волновым алгоритмом, начиная с верхнего левого угла, искомая величина - площадь нового поля минус число залитых ячеек, минус число единиц. | ||
|
Номер ответа: 2 Автор ответа: vito Разработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #2 | Добавлено: 16.10.06 19:31 |
| Можно так -же методом Монте-Карло подсчитать. | ||
|
Номер ответа: 3 Автор ответа: vitoРазработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #3 | Добавлено: 17.10.06 03:15 |
|
Вот простой примерчик метода Монте-Карло.
Для того чтобы уловить суть, достаточно. #include "stdafx.h"
#include "math.h" #include <time.h> int _tmain(int argc, _TCHAR* argv[] 
{ srand  time (0)) ;
int arr[5][7]={ 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0};// немного модифицированная кривая (6 пикселей внутри) int count=0, count1=0;// счетчики int rx,ry; // координаты (индексы массива) for (int i=0;i<10000;i++) // нечинаем итерации (чем больше - тем точнее результат) { rx=rand()%10;// генерим два случайных числа ry=rand()%10; if (ry<5 && rx<7)// попали в квалрат? { count++; if ((rx==1&& ry==4)||(rx==2&& ry==2)||(rx==2&& ry==3)||(rx==2&& ry==4)||(rx==3&& ry==3)||(rx==5&& ry==2)) // лениво было писать нормально (сделаешь если захочещь сам  )
// проверяем попадание в ограниченную линией фигуру count1++; // наращиваем счетчик } } double pl =(double) count1/(double)count;// вычсляем отношение (попавших- не попавших) double pl1 =(5*7)*pl; // вычисляем площадь (кол-во пикселей) printf( "Number pixel= %4.0f\n", pl1 ); // выводим = 6 return 0; } Надо иметь в виду, что результат имеет погрешность (оперируем случайными величинами). И опять этот мерзкий С.
|
||
|
Номер ответа: 4 Автор ответа: pinky ICQ: 218-538-334 Вопросов: 3 Ответов: 9 |
Web-сайт: Профиль | | #4 | Добавлено: 17.10.06 09:51 |
|
Можно сделать так (по ходу это то же самое что и предложил Sharp тока непонятно что такое волновой алгоритм
берем первую строку и начиная с первого элемента(если он равен нулю) все встретившиеся нули меняем на еденицы. делаем это до первой встретившейся еденицы, или до конца, если такой нет. если первый элемент равен 1 то ничего не делаем. то же самое делаем справа налево. потом считаем количество оставшихся нулей. |
||
|
Номер ответа: 5 Автор ответа: el-pasoВопросов: 3 Ответов: 164 |
Профиль | | #5 | Добавлено: 17.10.06 19:00 |
|
Function Solve() As Long ' ' как бы ввод Const h = 5 Const w = 7 Const s = "0001110,0111010,0100010,0111110,0000000" ' ' разбиваем текст в массив строк Dim a() As String: a = Split(s, ","
' Dim l As Integer ' счетчик строк Dim c As Integer ' счетчик символов в строке ' Dim CountZeroes As Boolean: CountZeroes = False ' флаг: надо ли считать нули Dim Zeroes As Integer: Zeroes = 0 ' количество накопленных ноликов ' ' проходим через все строки по очереди... For l = 0 To h - 1 ' ' сбрасываем флаг (первые ноли в строке никогда не считаются) CountZeroes = False ' ' прочесываем все символы в строке - с начала и до последней единицы (не включая ее) For c = 1 To InStrRev(a(l), "1" - 1
' ' если видим переход "10" переключаем флаг (True -> False, False -> True) If Mid$(a(l), c, 2) = "10" Then CountZeroes = Not CountZeroes ' если символ - нолик, и нолики следует считать, то считаем его If Mid$(a(l), c, 1) = "0" And CountZeroes Then Zeroes = Zeroes + 1 ' Next Next ' ' возвращаем результат Solve = Zeroes ' End Function |
||
|
Номер ответа: 6 Автор ответа: el-pasoВопросов: 3 Ответов: 164 |
Профиль | | #6 | Добавлено: 17.10.06 19:06 |
|
Хм.. Запостил, и прикинул, что есть баг )
Если матрица будет вида 1110111 1011101 1000001 1111011 0001110 то посчитает неверно... Надо подумать... |
||
|
Номер ответа: 7 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #7 | Добавлено: 17.10.06 20:01 |
|
vito, это прикол такой?
http://algolist.manual.ru/games/wavealg.php |
||
|
Номер ответа: 8 Автор ответа: vitoРазработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #8 | Добавлено: 17.10.06 23:19 |
|
Sharp
Почти. Ну считает-же.
Волновой алгоритм конечно оптимален. А это для разнообразия. |
||
|
Номер ответа: 9 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #9 | Добавлено: 18.10.06 17:21 |
| Ну в условии же не сказано, что единицы стоят всегда на одних и тех же позициях | ||
|
Номер ответа: 10 Автор ответа: vitoРазработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #10 | Добавлено: 18.10.06 22:43 |
|
Sharp
Ну в условии же не сказано, что единицы стоят всегда на одних и тех же позициях
Я немного суть не уловил. Из этого следует, что метод Монте - Карло не применим? |
||
|
Номер ответа: 11 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #11 | Добавлено: 18.10.06 23:06 |
| Точно не в таком виде, как у тебя. Потому что нужно динамически определять, находится ли точка внутри контура - прописать статически условие для этого не получится. | ||
|
Номер ответа: 12 Автор ответа: vitoРазработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #12 | Добавлено: 19.10.06 00:00 |
|
Sharp
Потому что нужно динамически определять, находится ли точка внутри контура -
У меня все очень криво (в общем и вправду развлекался, но это, все-же, проверяется динамически.
1.rx=rand()%10;// генерим два случайных числа ry=rand()%10; 2.if (ry<5 && rx<7)// попали в квалрат? 3. if ((rx==1&& ry==4)||(rx==2&& ry==2)||(rx==2&& ry==3)||(rx==2&& ry==4)||(rx==3&& ry==3)||(rx==5&& ry==2)) Вот здесь и проверяем попадание внутрь контура. Т.е в принципе получается динамическое определение на попадание точки внутрь контура. прописать статически условие для этого не получится.
Статическое условие получилось из-за рассмотрения частного случая (если я правильно понял суть). И конечно так метод Монте-Карло не реализуется. Просто частный случай. |
||
|
Номер ответа: 13 Автор ответа: el-pasoВопросов: 3 Ответов: 164 |
Профиль | | #13 | Добавлено: 19.10.06 00:23 |
|
Нде.. Написал.. Только выкладывать не буду, ибо код большой + класс.. И вообще простой VB для таких вещей не слишком подходит - лучше .NET :/
P.S. Волновой алгоритм рулит. |
||
|
Номер ответа: 14 Автор ответа: AndreyВопросов: 0 Ответов: 1 |
Профиль | | #14 | Добавлено: 06.11.06 00:58 |
|
Есть очень простое решение.
Допустим есть следующая фигура: 1110111 111 111 1011101 ===\ 1 111 1 1000001 ====> 1 1 1111011 ===/ 1111 11 0001110 111 Нули я убрал для наглюдности. X 333333333 333333333 0 X=9 311101113 3111 1113 1 Y=7 310111013 ===\ 31 111 13 2 310000013 ====> Y 31 13 3 311110113 ===/ 31111 113 4 300011103 3 111 3 5 333333333 333333333 6 012345678 Делаем рамку чтобы у каждой клетки были все четыре границы. Далее идёт сам просчет: Dim check as Boolean Dim i, j as Integer ' Тут стоит пояснить зачем нужна переменная check ' Алгоритм проверяет что нет ни одного нуля ' стоящего рядом с рамкой (3) или с другим нулем ' связанным с рамкой (4). Цикл завершится когда ' значение check будет положительно, тоесть когда ' все внешние нули поменяны на 4. While Not check check = True For j = 1 To Y - 2 'Проверка строчек 1-5 For i = 1 To X - 2 'Проверка символов 1-7 If m[j] = 0 Then 'Работать только с 0 If m[i-1][j] > 2 Or m[i+1][j] > 2 Or m[j-1] > 2 Or m[j+1] > 2 Then 'Если один из соседних символов рамка или 0 вне фигуры m[j] = 4 ' 4 это 0 вне фигуры check = False 'Выполнить проверку снова End If End If End For End For Wend Теперь у нас есть следующая картина: 333333333 333333333 0 X=9 311141113 311141113 1 Y=7 310111013 ===\ 31 111 13 2 310000013 ====> Y 31 13 3 311110113 ===/ 31111 113 4 344411143 344411143 5 333333333 333333333 6 Проходим циклом и ищем количество нулей. Вот и всё! |
||
Страница: 1 |