Форум русскоязычного сообщества Ubuntu


Увидели сообщение с непонятной ссылкой, спам, непристойность или оскорбление?
Воспользуйтесь ссылкой «Сообщить модератору» рядом с сообщением!

Автор Тема: Задачка для тренировки  (Прочитано 5603 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн obgorelyi

  • Автор темы
  • Новичок
  • *
  • Сообщений: 45
    • Просмотр профиля
Задачка для тренировки
« : 04 Июнь 2013, 17:44:10 »
Есть одна задачка, вроде бы и легкая, но меня она постоянно заставляет задуматься.
Нарисовать числовую змейку в массиве NxN (число N -нечетное) при том, так чтобы змейка закручивалась. Лучше на примере покажу:
[13, 14, 15, 16, 17]
[12,  3,  4,  5, 18]
[11,  2,  1,  6, 19]
[10,  9,  8,  7, 20]
[25, 24, 23, 22, 21]
Если посмотреть то цифры идут от центра и по спирали. Вот моя реализация на Python'е, интересно ваше мнение. Возможно, мое мнение плохое, так как я дилетант в программировании, ничего лучше придумать не смог.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

tp = 1
while tp:
  try:
    N = int(input("Введите число N: \n"))
    tp = 0
    break
  except:
    print("Ошибка: введенное значение не является целым числом!!!")
    tp=1


counter = 1
ring = 1
while ring<=N:
  # Первое кольцо
  if ring == 1:
    array = [[counter]]
    # Задаем направление закручивания
    left = 1
    #for ig in array:
      #print(str(ig))
    #print("\n")
  # Переходим ко всем остальным кольцам
  else:
    counter = counter+1
    left = 1
    low = len(array)-1
    # Влево
    array[low].insert(0,counter)
   
    #for ig in array:
      #print(str(ig))
    #print("\n")
   
   
    up = 1
    # Вверх
    while up <= (2*(ring-1)-1):
      counter = counter + 1
      if up == (2*(ring-1)-1):
          array.insert(0,[counter])
      else:
          low=low-1
          array[low].insert(0,counter)
      up = up+1
    #for ig in array:
      #print(str(ig))
    #print("\n")
   
    right = 1
    # Вправо
    while right<=2*(ring-1):
      counter = counter + 1
      array[0].append(counter)
      right = right+1
    #for ig in array:
      #print(str(ig))
    #print("\n")
   
    # Вниз
    down = 1
    high=0
    while down <= 2*(ring-1):
      counter = counter+1
      if down<2*(ring-1):
          high = high+1
          array[high].append(counter)
      else:
          array.append([counter])
      down = down + 1
    #for ig in array:
      #print(str(ig))
    #print("\n")
   
    # Снова налево
    while left<=(ring-1)*2:
      counter = counter + 1
      low = len(array)-1
      array[low].insert(0,counter)
      left=left+1
  ring = ring+1

for ig in array:
  print(str(ig))

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12075
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #1 : 04 Июнь 2013, 18:51:57 »
"Афтор не читатель, автор писатель"....

(Нажмите, чтобы показать/скрыть)

Тут имхо важно сформулировать алгоритм:
Есть начальная точка,
Есть (согласно концепции решения) граничные условия движения (вдоль чего двигаемся, где поворачиваем).
Вот дальше и строим цикл пока есть возможность движения (хоть в одну сторону нет ограничивающего условия).
Ну и как-то так.

PS а код я даже читать не стал прочитав пару комментариев ( # Первое кольцо и  # Переходим ко всем остальным кольцам).. Не верно это - нет там колец и нет первого и последнего - есть шаги движения.
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн obgorelyi

  • Автор темы
  • Новичок
  • *
  • Сообщений: 45
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #2 : 04 Июнь 2013, 22:32:01 »
Ну может вы это кольцами и не назовете, а для меня та змейка движется по кольцам, стартует из 1-го кольца, то бишь 1, и двигается дальше по 2-му, 3-му и т.д.

По поводу вашей истории, лично у меня терпения бы не хватило 2 месяца, что-то отлаживать (максимум 2-3 дня). Я в таких случаях начинаю, с чистого листа. Так проще и может еще и идея какая придет, как лучше сделать, а не как всегда :).

Пытался придумать, как с помощью списковых сборок собрать, такой массив, придумать не смог:(. Зато другая идея посетила, по треугольникам заполнить массив:
def suma(a):
  sumA = 0
  for ai in range(a+1):
    sumA = sumA+ai
  return sumA

array = []
for i in range(2*N-1):
  # Заполним левые полудиагонали
  if i < N:
    array.append([1+2*((N-i)-1)+8*suma(N-i-2)]) # Строка работает исправно, вплоть до 1
   
    # Заполним верхний треугольник
    for ik in range(2*N-2-2*i):
      array[i].append(array[i][ik]+1)
   
    # Заполним верхнюю половину правого треугольника
    for ig in range(i):
      array[i].insert(ig,array[i-1][ig]-1)
   
    # Заполним левую половину правого треугольника
    for ig in range(2*N-i-1,2*N-1):
      array[i].insert(ig,array[i-1][ig]+1)
  else:
    array.append([1+8*((i-N)+1)+8*suma(i-N)]) # Оно же квадраты нечетных чисел pow((2*(i-N+1)+1),2)
   
    # Заполним нижний треугольник
    for ik in range(2*(i-N)+2):
      array[i].append(array[i][ik]-1)
   
    # Заполним верхний левый треугольник
    for ig in range(2*N-i-2):
      array[i].insert(ig,array[i-1][ig]-1)
   
    # Заполним нижний левый треугольник
    for ig in range(i+1,2*N-1):
      array[i].insert(ig,array[i-1][ig]+1)
 
  # Вывод на экран
  print(str(array[i]))

Оффлайн Phlya

  • Старожил
  • *
  • Сообщений: 2219
  • Фля, Цыганский барон, Винни Пух
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #3 : 04 Июнь 2013, 22:52:37 »
Первый цикл нерационально сделан.
Код: Python
  1. tp = 1
  2. while tp: #Можно написать while True:, вообще без этого tp
  3.   try:
  4.     N = int(input("Введите число N: \n"))
  5.     tp = 0
  6.     break #Можно только этим обойтись, без обнуления tp
  7.   except:
  8.     print("Ошибка: введенное значение не является целым числом!!!")
  9.     tp=1 #А это просто не нужно
  10.  
« Последнее редактирование: 04 Июнь 2013, 23:04:16 от Phlya »
Ubuntu 14.04 (Unity), MSI GE40

Оффлайн obgorelyi

  • Автор темы
  • Новичок
  • *
  • Сообщений: 45
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #4 : 05 Июнь 2013, 05:06:31 »
Ну а как рационально сделать?
Первый цикл, это просто защита от очепяток, и выполнятся много раз он не будет. Если есть более рациональный способ проверки введенного значения подскажи.

Оффлайн Phlya

  • Старожил
  • *
  • Сообщений: 2219
  • Фля, Цыганский барон, Винни Пух
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #5 : 05 Июнь 2013, 10:16:40 »
Я там в комментариях к коду написал.
Ubuntu 14.04 (Unity), MSI GE40

Оффлайн Yurror

  • Старожил
  • *
  • Сообщений: 1966
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #6 : 05 Июнь 2013, 11:16:49 »
...
По поводу вашей истории, лично у меня терпения бы не хватило 2 месяца, что-то отлаживать (максимум 2-3 дня). Я в таких случаях начинаю, с чистого листа. Так проще и может еще и идея какая придет, как лучше сделать, а не как всегда :).
...
Работа программиста 99,9% нудная рутина. Лучше идти сразу в другую область.
Отлаживать это еще весело, а вот поддерживать быдлокод переписать котрый никто времени не даёт вот это нудно.

Оффлайн ArcFi

  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 15189
    • Просмотр профиля
    • aetera.net
Re: Задачка для тренировки
« Ответ #7 : 05 Июнь 2013, 16:35:28 »
Код: Bash
  1. #!/bin/bash
  2.  
  3. # Coded by: ArcFi <arcfi[at]aetera[dot]net>
  4. # License: GNU General Public License (GPL) version 3+
  5.  
  6. # Square Spiral
  7.  
  8. N="${1:-10}"
  9. K="$(expr length $((N**2))+1)"
  10.  
  11. for (( L=0 ; L<N ; L++ ))
  12. do
  13.         for (( C=0 ; C<N ; C++ ))
  14.         do
  15.                 if [ "$C" -ge "$L" -a "$C" -le "$((N-L-1))" ]
  16.                 then
  17.                         printf "% ${K}d" "$(((N-2*L)**2-3*(N-2*L-1)+C-L))"
  18.                 elif [ "$C" -ge "$L" -a "$C" -ge "$((N-L-1))" ]
  19.                 then
  20.                         printf "% ${K}d" "$(((N-2*C)**2-3*(N-2*C-1)+L-C))"
  21.                 elif [ "$C" -le "$L" -a "$C" -ge "$((N-L-1))" ]
  22.                 then
  23.                         printf "% ${K}d" "$(((N-2*(N-(L+1)))**2-1*(N-2*(N-(L+1))-1)-C+L))"
  24.                 elif [ "$C" -le "$L" -a "$C" -le "$((N-L-1))" ]
  25.                 then
  26.                         printf "% ${K}d" "$(((N-2*(N-(C+1)))**2-1*(N-2*(N-(C+1))-1)-L+C))"
  27.                 fi
  28.         done
  29.         echo
  30. done
  31.  
  32. exit 0

$ ./square-spiral.sh 7
  31  32  33  34  35  36  37
  30  13  14  15  16  17  38
  29  12   3   4   5  18  39
  28  11   2   1   6  19  40
  27  10   9   8   7  20  41
  26  25  24  23  22  21  42
  49  48  47  46  45  44  43

$ ./square-spiral.sh 8
  43  44  45  46  47  48  49  50
  42  21  22  23  24  25  26  51
  41  20   7   8   9  10  27  52
  40  19   6   1   2  11  28  53
  39  18   5   4   3  12  29  54
  38  17  16  15  14  13  30  55
  37  36  35  34  33  32  31  56
  64  63  62  61  60  59  58  57

Оффлайн obgorelyi

  • Автор темы
  • Новичок
  • *
  • Сообщений: 45
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #8 : 05 Июнь 2013, 16:50:09 »
to Plya: на комментарии внимания не обратил, думал это мои комментарии :).

tp поставил для надежности, просто был инцидент, когда запутался в куче циклов (писал на горячую, то есть сразу из головы, без особого обдумывания). И такой вариант с break, не прокатывал (требовался выход из нескольких циклов сразу)

код был примерно следующий (точно не помню), теперь привычкой tp ставлю:
tp=1
while tp:
    # операторы
    while tp:
        # операторы
        while tp:
            # операторы
            if (условие):
                tp = 0


to ArcFi: эх, долго мне до вас расти, не додумался я до алгоритма всего лишь с двумя циклами. :)

********
Плохая штука невнимательность. После того, как описал вариант с диагоналями я понял (а точнее, когда посмотрел, что идет дальше после объявления циклов), в чем соль вашего алгоритма.
« Последнее редактирование: 17 Июнь 2013, 21:30:52 от obgorelyi »

Оффлайн ArcFi

  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 15189
    • Просмотр профиля
    • aetera.net
Re: Задачка для тренировки
« Ответ #9 : 05 Июнь 2013, 17:27:57 »
obgorelyi, вообще, достаточно одного цикла. ;)
Число можно сразу писать по заданным координатам (строка, столбец) и поворачивать при достижении угловой точки.

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12075
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #10 : 05 Июнь 2013, 18:32:21 »
obgorelyi, вообще, достаточно одного цикла. ;)
Число можно сразу писать по заданным координатам (строка, столбец) и поворачивать при достижении угловой точки.
Ага и я это ему говорил - но у него меньше чем на кольца - задача не декомпозируется... бЯда  :'(


По поводу вашей истории, лично у меня терпения бы не хватило 2 месяца, что-то отлаживать (максимум 2-3 дня). Я в таких случаях начинаю, с чистого листа. Так проще и может еще и идея какая придет, как лучше сделать, а не как всегда :).
Ну я и так длинно написал.... Там таки да - код не раз переписывался с нуля в ходе тех двух месяцев, результат только не менялся - неотлаживаем CASE-код даже для такой простой грамматики как у LISP. Ну так есть механизм роботов - он для того и был разработан, что бы грамматики лопать... но там надо сначала нарисовать граф, постороить таблицу переходов.... а мне то хотелось - просто закодить все сразу, по быстрому, без картинок "ненужных".... Так и тут... Порисовав картинки - сразу бы было понятно что есть пошаговый обход с условиями поворота....
« Последнее редактирование: 05 Июнь 2013, 18:39:20 от Sly_tom_cat »
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн obgorelyi

  • Автор темы
  • Новичок
  • *
  • Сообщений: 45
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #11 : 05 Июнь 2013, 23:00:12 »
Тут имхо важно сформулировать алгоритм:
Есть начальная точка,
Есть (согласно концепции решения) граничные условия движения (вдоль чего двигаемся, где поворачиваем).
Вот дальше и строим цикл пока есть возможность движения (хоть в одну сторону нет ограничивающего условия).
Ну и как-то так.

Как я понял, это речь про алгоритм в один цикл. Честно сказать, я не сразу понял, о чем это речь, и к чему это вообще внимание почему-то заострил на кольцах. Реализацию в один цикл сделать попробую, когда освобожусь от курсовых.

to Sly_tom_cat: Возник вопрос, что за механизм роботов (гугль выдает механику роботов)? Просто судя по дальнейшему описанию похоже на теорию автоматов. Тоже составляешь граф по алгоритму, таблицу переходов и т.д. Как применить это к цифровой электронике знаю, а вот как это при программировании использовать, для меня вопрос.

Оффлайн inkblack

  • Старожил
  • *
  • Сообщений: 1216
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #12 : 05 Июнь 2013, 23:47:53 »
...

to Sly_tom_cat: Возник вопрос, что за механизм роботов (гугль выдает механику роботов)? Просто судя по дальнейшему описанию похоже на теорию автоматов. Тоже составляешь граф по алгоритму, таблицу переходов и т.д. Как применить это к цифровой электронике знаю, а вот как это при программировании использовать, для меня вопрос.

ru.wikipedia.org/wiki/Конечный_автомат — вы про это?

Пользователь решил продолжить мысль 06 Июнь 2013, 00:10:13:
...

to ArcFi: эх, долго мне до вас расти, не додумался я до алгоритма всего лишь с двумя циклами. :)

Это не «алгоритм с двумя циклами». Это задача сведена от «поворачиваем направо,
поворачиваем налево» к ответу на вопрос:

Дана квадратная матрица N x N, в ней числа расположены «по спирали», как вы показали
в первом сообщении. А вопрос такой: чему равен элемент матрицы a(i,j)? Надо написать
формулу вида a = F(i, j, N).

ArcFi сделал именно это. (Правда, на Баше :\ ) А дальше всё просто: распечатываем
матрицу по строкам. Двумя циклами удобно. Внутренний цикл печатает числа одной строки,
внешний цикл печатает строки, одну за другой.

А расти надо, кстати, совсем в другой области. В математике. Именно она поможет вам
увидеть суть подобных задач.

И количество циклов здесь — не самоцель. Гораздо важнее научиться писать ясный и
обслуживаемый код.
« Последнее редактирование: 06 Июнь 2013, 00:10:13 от inkblack »
Делюсь знаниями, но их у меня мало!

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12075
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #13 : 06 Июнь 2013, 11:50:31 »
to Sly_tom_cat: Возник вопрос, что за механизм роботов (гугль выдает механику роботов)? Просто судя по дальнейшему описанию похоже на теорию автоматов. Тоже составляешь граф по алгоритму, таблицу переходов и т.д. Как применить это к цифровой электронике знаю, а вот как это при программировании использовать, для меня вопрос.
Ну да, грешу - вру на ходу - не роботы, автоматы (старею что-ли... институт то закончил в 1995  :-[ ).

Так вот, если графом описать возможные грамматические схемы языка, то принимая на входе текст программы на этом языке переход осуществляется по лексеме (лексема - элементарный элемент - ключевое слово или спец символы - скобочки, запятые и т.п.) тогда конечные состояния будут соответствовать полностью принятой конструкции языка. Любого рода вложенность реализуется рекурсивным разбором вложенных конструкций новым экземпляром того-же автомата. Если принимаемая лексема не соответствует ожидаемой - то налицо нарушение грамматики (синтаксическая ошибка). Ну, а под разобранную конструкцию просто пишется код исполняющий те действия, которые соответствуют этой конструкции. Дальше собственно два вариант - либо этот код выполняем (интерпретатор) либо сохраняем, что бы исполнить потом (компилятор).
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн f-dzmitry

  • Участник
  • *
  • Сообщений: 168
    • Просмотр профиля
Re: Задачка для тренировки
« Ответ #14 : 06 Июнь 2013, 14:38:52 »
Ну да, грешу - вру на ходу - не роботы, автоматы (старею что-ли... институт то закончил в 1995  :-[ ).
Значит пора на пенсию! :)
void next(){next();};

 

Страница сгенерирована за 0.092 секунд. Запросов: 24.