Форум программистов, компьютерный форум, киберфорум
Наши страницы
нтч
Войти
Регистрация
Восстановить пароль
+++
Недостающую глубину мысли обычно компенсируют её длиной.
+++
Оценить эту запись

Сложный алгоритм

Запись от нтч размещена 06.08.2018 в 13:43
Обновил(-а) нтч 06.08.2018 в 13:50 (добавлено примечание)

Мне не удалось до конца решить эту задачу. Алгоритм оказался каким-то диким. Вероятно он не совсем понимает, что ... ТАМ В КОММЕНТАРИИ ЕСТЬ ПОЛНОЕ РЕШЕНИЕ. ПРОВЕРЬТЕ.

Суть задачи заключается в следующем.
1. даны две квадратные матрицы размером 5 × 5, заполненные случайно целыми числами 0; 1; 2; 3; 4
2. матрицы обозначены x() и y()
3. надо произвести с ними действия (алгоритм описан ниже), чтобы получить квадратную матрицу z() размером 5 × 5

АЛГОРИТМ
1. сравниваются (в двойном цикле) элементы x(i, j) и y(i, j)
2. если оба элемента чётные, то они складываются (сумма идет в z(i, j))
3. если оба элемента нечётные, то вычисляется модуль разности этих элементов
4. если первый элемент чётный, а второй нечётный, то происходит умножение
5. если первый элемент нечётный, а второй чётный, то вычисляется целочисленное деление

(более подробно о)
ЦЕЛОЧИСЛЕННОЕ ДЕЛЕНИЕ
6. итак, если деление возможно, то оно вычисляется
7. если деление невозможно, то в качестве делителя (в программе он обозначен как del) выступает сумма элементов вокруг y(i, j) (всего максимум 8 элементов, минимум 3 (это если элемент находится в углу матрицы))
8. если и в этом случае деление невозможно, то в качестве делителя выступает вторая сумма элементов, окружающая первые элементы (их максимум 16)
9. и так далее. Предполагается, что вторая матрица может состоять из одних нулей (вероятность такого события невелика, но ведь числа случайные). В этом случает должна быть выведена на экран надпись "ЗАДАЧА НЕРАЗРЕШИМА"
10. если задача имеет решение, то печатаются все матрицы

Главная проблема заключается в том, что
1. надо сразу (или динамически) увеличит размер матрицы y()
2. для элемента y(i, j) надо написать функцию, которая могла бы вычислить сумму элементов, для которых элемент y(i, j) является центральным. Вот тут совсем неясно что делать? В общем ясно, что не ясно.

Привожу вам часть кода, который решает часть задачи до конца, но не весь алгоритм.

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
CLS
RANDOMIZE TIMER
 
n = 5
DIM x(n, n)
DIM y(n + 1, n + 1)
DIM z(n, n)
 
FOR i = 1 TO n
FOR j = 1 TO n
   x(i, j) = INT(5 * RND)
   y(i, j) = INT(5 * RND)
   PRINT x(i, j);
NEXT: PRINT
NEXT: PRINT
 
FOR i = 1 TO n
FOR j = 1 TO n
   PRINT y(i, j);
NEXT: PRINT
NEXT: PRINT
 
FOR i = 1 TO n
FOR j = 1 TO n
   A = x(i, j) MOD 2 = 0
   B = x(i, j) MOD 2 = 1
   C = y(i, j) MOD 2 = 0
   D = y(i, j) MOD 2 = 1
 
   IF A AND C THEN
      z(i, j) = x(i, j) + y(i, j)
   ELSEIF B AND D THEN
      z(i, j) = ABS(x(i, j) - y(i, j))
   ELSEIF A AND D THEN
      z(i, j) = x(i, j) * y(i, j)
   ELSEIF B AND C AND y(i, j) <> 0 THEN
      z(i, j) = x(i, j) \ y(i, j)
   ELSE
      FOR p = i - 1 TO i + 1
      FOR q = j - 1 TO j + 1
         del = del + y(p, q)
      NEXT
      NEXT
 
      z(i, j) = x(i, j) \ del
   END IF
NEXT
NEXT
 
FOR i = 1 TO n
FOR j = 1 TO n
   PRINT z(i, j);
NEXT: PRINT
NEXT: PRINT
END
Примечание
мне кажется, что часть кода связанная с делением должна быть выделена в специальную рекурсивную процедуру. Или хотя бы в обычную процедуру.
Размещено в Без категории
Просмотров 165 Комментарии 7
Всего комментариев 7
Комментарии
  1. Старый комментарий
    Аватар для diadiavova
    Цитата:
    надо сразу (или динамически) увеличит размер матрицы y()
    И сразу вопрос: зачем?
    Цитата:
    для элемента y(i, j) надо написать функцию, которая могла бы вычислить сумму элементов, для которых элемент y(i, j) является центральным. Вот тут совсем неясно что делать? В общем ясно, что не ясно.
    Самый простой вариант - это выделение прямоугольника в массиве и нахождение суммы его элементов в двойном цикле. Границы прямоугольника вычисляются довольно просто, но они зависят от уровня, поэтому алгоритм будет рекурсивным. На первом уровне границы координаны x определяются прибавлением и вычитанием единицы к абсциссе центральной ячейки. Границы y - то же самое для ординаты. На втором уровне будем прибавлять-вычитать двойку и т. д. Если граница получилась меньше единицы, то устанавливаем единицу, если больше пяти - пять. После обхода в циклах, если сумма больше нуля - возвращаем ее, в ином случае вызываем функцию рекурсивно до тех пор, пока либо границы обхода не поглотят всю матрици, либо будет получено отличное от нуля значение.
    Кубасика я не знаю, но могу приблизительно набросать на VB.Net. У тебя там, насколько я понимаю, массив индексируется с единицы, а не с нуля, я это учел. Код расписал подробно, так что понять идею будет несложно. Правда будет ли это работать - не знаю, поскольку не проверял.
    vb.net
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    
    Function GetNearestSum(mx, x, y, level)
        Dim xMin = IIf(x - level < 1, 1, x - level)
        Dim xMax = IIf(x + level > 5, 5, x + level)
        Dim yMin = IIf(y - level < 1, 1, y - level)
        Dim yMax = IIf(y + level > 5, 5, y + level)
        Dim sum = 0
        For i = xMin To xMax
            For j = yMin To yMax
                sum = sum + mx(i, j)
            Next j
        Next i
        If (xMin = 1 And yMin = 1 And xMax = 5 And yMax = 5) Or sum <> 0 Then
            GetNearestSum = sum
        Else
            GetNearestSum(mx, x, y, level + 1)
        End If
    End Function
    Здесь первый аргумент - сама матрица, далее координаты центральной ячейки, последний - уровень, ему изначально надо задать значение 1. Наверное целесообразнее было сделать его необязательным, но я не знаю есть ли такое в кубасике, так что не стал вставлять в код потенциально непонятные элементы.
    Запись от diadiavova размещена 07.08.2018 в 13:52 diadiavova вне форума
  2. Старый комментарий

    Полный код решения задачи

    Уважаемый diadiavova,
    спасибо вам за комментарий. Я проанализировал ваш код и написал следующую программу.
    1. Стоит отметить, что матрицу y() я сделал глобальной по видимости и сразу увеличил ее до максимального размера. QBasic позволяет задавать интервал изменения индекса. В этой задаче интервал от -3 до 9.
    2. если ничего не напутал, то программа работает правильно. Я даже проверил ее, сделав y() полностью нулевой матрицей и программа сообщила, что задача Не разрешима (RESHENIY NET)
    3. Еще раз очень вам благодарен. Ибо ваш код заставил мои мозги работать в нужном направлении.

    QBasic/QuickBASIC
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    
    DECLARE FUNCTION SUM! (ix!, jx!, k!)
    CLS
    RANDOMIZE TIMER
     
    n = 5
    DIM x(n, n)
    DIM SHARED y(-3 TO 9, -3 TO 9)
    DIM z(n, n)
     
    FOR i = 1 TO n
    FOR j = 1 TO n
       x(i, j) = INT(5 * RND)
       y(i, j) = INT(5 * RND)
       PRINT x(i, j);
    NEXT: PRINT
    NEXT: PRINT
     
    FOR i = 1 TO n
    FOR j = 1 TO n
       PRINT y(i, j);
    NEXT: PRINT
    NEXT: PRINT
     
    FOR i = 1 TO n
    FOR j = 1 TO n
       A = x(i, j) MOD 2 = 0
       B = x(i, j) MOD 2 = 1
       C = y(i, j) MOD 2 = 0
       D = y(i, j) MOD 2 = 1
     
       IF A AND C THEN
          z(i, j) = x(i, j) + y(i, j)
       ELSEIF B AND D THEN
          z(i, j) = ABS(x(i, j) - y(i, j))
       ELSEIF A AND D THEN
          z(i, j) = x(i, j) * y(i, j)
       ELSEIF B AND C AND y(i, j) <> 0 THEN
          z(i, j) = x(i, j) \ y(i, j)
       ELSE
          del = SUM(i, j, 1)
     
          IF del <> 0 THEN
             z(i, j) = x(i, j) \ del
          ELSE
             PRINT "RESHENIY NET"
             GOTO end2
          END IF
       END IF
    NEXT
    NEXT
     
    FOR i = 1 TO n
    FOR j = 1 TO n
       PRINT z(i, j);
    NEXT: PRINT
    NEXT: PRINT
    end2:
    END
     
    FUNCTION SUM (ix, jx, k)
       IF k > 4 THEN EXIT FUNCTION
     
       FOR i = ix - k TO ix + k
       FOR j = jx - k TO jx + k
          S = S + y(i, j)
       NEXT
       NEXT
     
       IF S = 0 THEN
          SUM = SUM(ix, jx, k + 1)
       ELSE
          SUM = S
       END IF
    END FUNCTION
    Запись от нтч размещена 07.08.2018 в 16:04 нтч вне форума
  3. Старый комментарий
    diadiavova,
    вы гений, если вам этого никто не говорил, то я скажу.
    Запись от нтч размещена 07.08.2018 в 16:08 нтч вне форума
  4. Старый комментарий
    Аватар для diadiavova
    Цитата:
    Сообщение от нтч Просмотреть комментарий
    diadiavova,
    вы гений, если вам этого никто не говорил, то я скажу.
    Да нет, сегодня уже сказали ))
    Цитата:
    Сообщение от olya_p Посмотреть сообщение
    diadiavova, Вы - гений!
    Запись от diadiavova размещена 07.08.2018 в 16:34 diadiavova вне форума
  5. Старый комментарий
    Аватар для diadiavova
    По поводу матрицы, заполненной нулями: она должна вернуть ноль, мне показалось, что это логично, поскольку условия заданы так, что при нулевом значении ищутся ячейки вокруг и при последнем заходе складываемые ячейки все равно будут нулевыми. В принципе можно было задать другое значение, но я подумал, что все равно ведь делить на это число надо, ну так деление и должно вызывать ошибку.
    Запись от diadiavova размещена 07.08.2018 в 16:38 diadiavova вне форума
  6. Старый комментарий
    diadiavova,
    хорошо я буду вторым человеком, который сказал вам это.
    примечание
    Я хорошо знаю, как сложно решить сложную задачу, да еще если она написана на языке каменного века (а в школах от него еще не отказались однако). Хотя мне этот язык нравится. Он позволяет не тратить (не ломать мозги) на грамматику и многое другое. А высокой скорости в подобных задачах не требуется.
    Запись от нтч размещена 07.08.2018 в 16:48 нтч вне форума
  7. Старый комментарий
    diadiavova,
    конечно вы правы насчет нулевой матрицы. Но тут алгоритм составлен так, что до деления на 0 дело не доходит. Просто происходит выход из всех циклов и выдается сообщение.
    Запись от нтч размещена 07.08.2018 в 16:53 нтч вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru