19 апреля 2020

Пара алгоритмических задач для успешного программиста: нарисовать змейку, выстроить зиккурат

Пишу, перевожу и иллюстрирую IT-статьи. На proglib написал 140 материалов. Увлекаюсь Python, вебом и Data Science. Открыт к диалогу – ссылки на соцсети и мессенджеры: https://matyushkin.github.io/links/ Если понравился стиль изложения, упорядоченный список публикаций — https://github.com/matyushkin/lessons
Внутри поста две алгоритмические головоломки. Предложите в комментариях самое быстрое/лаконичное решение на любимом языке программирования – покажите класс!
21
Пара алгоритмических задач для успешного программиста: нарисовать змейку, выстроить зиккурат


Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

  1. углубишься в решение практических задач;
  2. узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

Ты также будешь на связи с преподавателем и другими студентами.

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

***

В конце марта Библиотека программиста опубликовала суперподборку более, чем 70 бесплатных русскоязычных курсов. Стараясь не отставать от читателей, мы сами штудируем курсы. Мимоходом попадаются занимательные задачки, решение которых доставляет подлинное удовольствие.

Ниже пара таких задач – мы предлагаем вам попробовать их решить и поделиться программным кодом в комментариях! Для решения можно использовать любой язык программирования. Даже в одном и том же языке можно применять абсолютно разные подходы – было бы интересно сравнить, как они различаются по скорости выполнения.

Подсказка к обеим задачам

В комментариях действует Markdown-разметка – для вставки форматированного кода ограничьте его с двух сторон тройными апострофами:

        Краткое описание идеи.

```
Программный код вашего решения.
```
    

Рисуем змейку 🐍

Задача: напишите функцию, которая принимает число n и выводит таблицу размером n * n, заполненную числами от 1 до n2 по спирали, выходящей из левого верхнего угла и закрученной по часовой стрелке.

Пример. Пусть n = 5, функция должна вернуть матрицу вида

        1  2  3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
    

Эту задачу мы повстречали в курсе «Программирование на Python». Если вы зайдёте в тупик – наводки можно найти в обсуждении задания. Попробуйте решить компактно и без дублирования кода.

Строим зиккурат 🏗️🔲📐

Задача: напишите функцию, которая принимает целое число n и выводит «ступенчатую» матрицу, состоящую из n «этажей». Этажи нумеруются с первого, ширина ступеньки равна одной строке или столбцу.

Пример. Пусть n = 4, функция должна вернуть матрицу вида

        1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 2 3 3 3 2 1
1 2 3 4 3 2 1
1 2 3 3 3 2 1
1 2 2 2 2 2 1
1 1 1 1 1 1 1
    

Данную головоломку мы нашли в курсе «Основы программирования на R». Если у вас возникли трудности, посмотрите комментарии обсуждения задания (в них есть специфика применения R). Особый интерес вызывает решение без циклов и рекурсий.

***

Хочу ещё таких задач! 💻

Если вам по вкусу подобные задачки, обратите внимание на наш сериал головоломок из 15 серий. В каждой серии новая задача и подробный ответ на предыдущую:

  1. Двойные фамилии (комбинаторика)
  2. Спрятанное решение (арифметический ребус)
  3. Остров хамелеонов (алгоритмы)
  4. Номер Тьюринга (комбинаторика)
  5. Время великих учёных (алгоритмы)
  6. Прогуливающиеся джентльмены (логика)
  7. Часы с одинаковыми стрелками (самая популярная)
  8. Вирус в колонии бактерий (алгебраическая задача)
  9. Шесть шахматных коней (задача на алгоритмы по теории графов)
  10. Задача о беглеце (динамическое программирование)
  11. Чеширский Кот и число палиндромов (комбинаторика)
  12. Карточная головоломка Конвея (алгоритм сортировки)
  13. Как ограбить банк? (динамическое программирование и шифры)
  14. Головоломка о лягушках (алгоритмы)
  15. Задача Сфинкса о разрезании лестниц (алгоритмы)
Больше полезной информации вы найдете на наших телеграм-каналах «Библиотека программиста» и «Книги для программистов».

Комментарии

 
07 ноября 2021

First task, JS

function snakeMatrix(n) {  
    /*создание массива размерности n*n */
    let arr = new Array(n);
    for (let i = 0; i < n ; i++)
        arr[i] = new Array(n);

    let line = [0, 0];//для хранения текущих координат
    let n_line = 1;//для переключения между строкой и столбцом

    let oper = [-1, 1];//для увеличения или уменьшения индексов
    let n_oper = 1;//для переключения с + на -

    let val = 0;//значение для инициализации элемента массива
    let count_item = 0;//счетчик элементов
    let count_line = 0;//счетчик линий

    while(1) {
        arr[ line[0] ][ line[1] ] = ++val;   
        if (++count_item > n - 1) {
            ++count_line % 2 && n-- || ( n_oper = +!n_oper );
            count_item = 0;
            n_line = +!n_line;
            if (n < 1) break;
        } 
        line[n_line] += oper[n_oper];
    }
    return arr;
}
console.log( snakeMatrix(5) );
04 августа 2020

вариант первой задачи на Python (адаптируемый под вторую)


def print_m(matrix):
    for row in matrix:
        for col in row:
            print(f"{col:4}",end=' ')
        print()

def snake(n):
    if n<=0:
        print("N должно быть > 0")
        return
    matrix = [[(x == y and 1 or 0) for y in range(n)] for x in range(n)]
    depth = ((n - 1) // 2) + 1
    around = []
    for i in range(depth):
        right = [[x, y] for x in [i] for y in range(n - i)[i:n - i - 1:]]
        down = [[x, y] for x in range(n - i)[i:n - i - 1:] for y in [n - i - 1]]
        left = [[x, y] for x in [n - i - 1] for y in range(n - i)[n - i - 1:i:-1]]
        up = [[x, y] for x in range(n - i)[n - i - 1:i:-1] for y in [i]]
        around += right + down + left + up
        if i == n - i - 1:
            around += [[i,i]]

    count = 1
    for j in around:
        matrix[j[0]][j[1]] = count
        count +=1
    print_m(matrix)

snake(11)
14 июня 2020

Обе задачи в плюсах

#include<iostream>
using namespace std;

class ROBOT
{
    public:
    ROBOT(): nap(0),krug(0),x(0),y(0) {}
    int nap;
    int krug;
    int x;
    int y;
};

int main(void)
{
cout<<"Тип игры:"<<endl<<"1 - змейка"<<endl<<"2 - зиккурат"<<endl;
int tip_igry;
cin>>tip_igry;
cout<<"размер:"<<endl;
int n;
cin>>n;
int arr[n][n];
int count=1;
ROBOT robot;

for(int schet=0;schet<n*n;schet++)
{
switch(robot.nap)
    { 
        case 0: 
            arr[robot.x++][robot.y]=count++;
            if(robot.x+1 == n-robot.krug) robot.nap++;
            break; 
        case 1: 
            arr[robot.x][robot.y++]=count++;
            if(robot.y+1 == n-robot.krug) robot.nap++;
            break; 
        case 2: 
            arr[robot.x--][robot.y]=count++;
            if(robot.x == robot.krug) robot.nap++;
            break; 
        case 3: 
            arr[robot.x][robot.y--]=count++;
            if(robot.y == 1+robot.krug) robot.nap++;
            break;     
    } 
if(tip_igry-1)
    count=robot.krug+1;
if(robot.nap>3) 
    {
        robot.nap=0;
        robot.krug++;
    }
}

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
        cout<<arr[j][i]<<' ';
    cout<<endl;
}
return 0;
}
10 июня 2020

Версия на Intel ASM под intel 8086. Очень маленькая по размеру бинарника. Имеет ограничение по размеру змейки - размер от 1 до 9

.MODEL  TINY

; link with flag /n

.DATA
    STEPS   DW 0, 0, 0, 0
    DELTAS  DW 2, 0, -2, 0

    ARR     DW 81 DUP(0)
    N       DW ?
    _10     DB 10
.CODE
print   PROC
    ADD     DL, 48
    MOV     AH, 02h
    INT     21h
    RET
print   ENDP

traverse    PROC
    MOV     CX, STEPS[BX]       ; КОЛИЧЕСТВО ШАГОВ
    MOV     AX, DELTAS[BX]      ; РАЗМЕР ШАГА
    _loop_travel:
        ADD     SI, AX          ; СЛЕДУЮЩИЙ ЭЛЕМЕНТ
        MOV     ARR[SI], DX     ; ПОМЕСТИЛИ ЧИСЛО
        INC     DX              ; УВЕЛИЧИЛИ ЧИСЛО
    LOOP    _loop_travel

    SUB     STEPS[BX], 2        ; В СЛЕДУЮЩИЙ РАЗ ПРОЙДЕМ НА 2 ШАГА МЕНЬШЕ
    ADD     BX, 2               ; СДВИНУЛИСЬ НА СЛЕДУЮЩИЙ ИНДЕКС
    RET
traverse    ENDP

main    PROC
    MOV     AX, 
    MOV     DS, AX

    ;---N=---
    MOV     DL, 'N' - 48
    CALL    print

    MOV     DL, '=' - 48
    CALL    print
    ;---N=---

    ;AX = N
    DEC     AH
    INT     21h
    SUB     AX, 304

    MOV     N, AX

    ; AX = N*2
    SAL     AX, 1
    MOV     DELTAS + 2, AX  ; ВПРАВО ПРОПУСКАЕМ СТРОКИ
    NEG     AX
    MOV     DELTAS + 6, AX  ; ВЛЕВО ПРОПУСКАЕМ СТРОКИ

    MOV     DX, 1           ; САМИ ЧИСЛА 1-N^2
    MOV     SI, -2          ; ИНДЕКС В МАССИВЕ

    ; ИНИЦИАЛИЗИРУЕМ КОЛИЧЕСТВО ШАГОВ В КАЖДУЮ СТОРОНУ
    MOV     AX, N
    MOV     STEPS, AX       ; ВПРАВО СНАЧАЛА N ШАГОВ

    DEC     AX
    MOV     STEPS+2, AX     ; ВНИЗ СНАЧАЛА N-1 ШАГ
    MOV     STEPS+4, AX     ; ВЛЕВО СНАЧАЛА N-1 ШАГ

    DEC     AX
    MOV     STEPS+6, AX     ; ВВЕРХ N-2 ШАГА

    _fill_loop:
        ; LEFT=>RIGHT
        MOV     BX, 0
        CALL    traverse

        ; UP=>DOWN
        ;MOV     BX, 2
        CMP     STEPS[BX], 0
        JE      _print_mat
        CALL    traverse

        ; LEFT<=RIGHT
        ;MOV     BX, 4
        CALL    traverse

        ; UP<=DOWN
        ;MOV     BX, 6
        CMP     STEPS[BX], 0
        JE      _print_mat
        CALL    traverse
    JMP     _fill_loop

    _print_mat:
    MOV     SI, 0
    MOV     CX, N
    _print_outer:
        PUSH    CX

        MOV     DL, 10-48
        CALL    print

        MOV     CX, N
        _print_inner:
            MOV     AX, ARR[SI]
            DIV     _10
            MOV     BX, AX

            MOV     DL, BL
            CALL    print

            MOV     DL, BH
            CALL    print

            MOV     DL, ' ' - 48
            CALL    print

            ADD     SI, 2
        LOOP    _print_inner
        POP     CX

    LOOP    _print_outer
    MOV     AX, 4C00h
    INT     21h
main    ENDP
END     main
22 мая 2020

Если надо сразу выводить змейку на печать, без массива, то придётся малость посчитать. Старый добрый Pascal/Delphi

for j:=1 to n do begin
  for i:=1 to n do begin
    z:=min(i,min(j,min(n+1-i, n+1-j))); //высота ступеньки пирамиды
    m:=n+2-2*z; //длина стороны внутреннего квадрата
    s:=n*n-m*m; //площадь нижних ступенек = начало оборота змейки
    if j=z then
      s:=s+i-z+1 //верх
    else if i=n-z+1 then
      s:=s+m+j-z //право
    else if j=n-z+1 then
      s:=s+3*m-i+z-2 //низ
    else
      s:=s+4*m-j+z-3; //лево
    write(s:4)
  end;
  writeln;
end;
18 мая 2020

life is pain without basic ! Option Base 1 Sub snake() Dim asd As Variant Dim NAR As Variant Range("A1").CurrentRegion.Delete

n = 10 ReDim asd(n ^ 2) ReDim NAR(n, n)

For i = 1 To n ^ 2 asd(i) = i Next i

a = 1 c = 1 x = 1 y = 1 flag = 1

For i = 1 To n ^ 2

 If a = n Then
    a = 1
    If flag = 1 Then
        flag = 2
        ElseIf flag = 2 Then
        flag = 3
        ElseIf flag = 3 Then
        flag = 4
        ElseIf flag = 4 Then
        flag = 1
        x = x + 1
        y = y + 1
        n = n - 2
    End If

End If

If flag = 1 Then
    NAR(x, y) = asd(c)
    c = c + 1
    a = a + 1
    y = y + 1
End If

If flag = 2 Then
    NAR(x, y) = asd(c)
    c = c + 1
    a = a + 1
    x = x + 1
End If

If flag = 3 Then
    NAR(x, y) = asd(c)
    c = c + 1
    a = a + 1
    y = y - 1
End If

If flag = 4 Then
    NAR(x, y) = asd(c)
    c = c + 1
    a = a + 1
    x = x - 1
End If

Next i

Range("A1").Resize(UBound(NAR, 1), UBound(NAR, 2)).Value = NAR

End Sub

06 мая 2020

Змейка на python

n = input('write message: ')
n = int(n)
#create snake
m = [[0 for y in range(n)] for x in range(n)]
i = 0
j = 0
d = 0
z = 1
zi = 0
nn = n-1
napr = [[0,1],[1,0],[0,-1],[-1,0]]
for k in range(1, n*n+1):
    try:
        if (m[i + napr[zi][0]][j + napr[zi][1]] != 0):
            z = (z%4) + 1
            zi = z - 1
            d += 1
            if d == 4:
                nn -= 1
                d = 0
    except:
        z = (z%4) + 1
        zi = z - 1
        d += 1
        if d == 4:
            nn -= 1
            d = 0       
    m[i][j] = k
    i += napr[zi][0]
    j += napr[zi][1]
#show snake
for j in range(n):  
    m1 = list(map(str,m[j]))
    print('\t'.join(m1))
    print('\n')
26 апреля 2020
const N = parseInt(process.argv[2]) || 3;
const itemLength = `${N}`.length + 1;
const repeater = ' '.repeat(itemLength);
const identity2 = (_, i) => i;
const getArray = (length, f = identity2) => Array.from({length}, f);
const item = i => () => N - i;
const result = getArray(N).slice(1).reduce((mx, i) => [
    getArray(i * 2 + 1, item(i)),
    ...mx.map(line => [item(i)(), ...line, item(i)()]),
    getArray(i * 2 + 1, item(i))
], [[N]]).map(line => line.map(
    item => `${repeater}${item}`.slice(-itemLength)
).join('')).join('\n');
console.log(result);
23 апреля 2020
def snake(n):
    arr = [[0 for x in range(n)] for y in range(n)]
    index = 0
    x = -1
    y = 0
    sign = 1
    while n > 0:
        for _ in range(n):
            x += sign
            index += 1
            arr[y][x] = index
        n -= 1
        for _ in range(n):
            y += sign
            index += 1
            arr[y][x] = index
        sign *= -1
    return arr

def ziggurat(n):
    lst = list(range(1, n + 1)) + list(range(n - 1, 0, -1))
    return [[min(x, y) for x in lst] for y in lst]

def pprint(arr):
    for row in arr:
        print(' '.join((str(i) for i in row)))

if __name__ == '__main__':
    pprint(snake(5))
    pprint(ziggurat(3))
22 апреля 2020

При попытке изменить комментарий эта ссылка не работает

22 апреля 2020

Для задачи о змейке, решение на питон:


a=[[0]*n for i in range(n)]
i=0
j=-1
b=1
m=0
while b<n**2:
    while j<n-m-1: 
        i=m
        j+=1
        a[i][j]=b
        b+=1
    while i<n-m-1:
        i+=1
        j=-m-1
        a[i][j]=b
        b+=1
    while j>-n+m:
        j-=1
        i=-m-1
        a[i][j]=b
        b+=1
    while i>-n+m+1:
        i-=1
        j=m
        a[i][j]=b
        b+=1
    m+=1
if n%2!=0:
    a[n//2][n//2]=n**2

for i in range(n):
    for j in range(n):
        if j==n-1:
            print(a[i][j],end="\n")
        else:
            print(a[i][j], end=" ")```
 
22 апреля 2020

1 Задача:

def draw_snake(n):
    x = 0
    y = 0
    k = 1
    rows_filled = 0
    cols_filled = 0
    direction = 1

    result = [[0 for _ in range(n)] for _ in range(n)]

    while k < n ** 2:

        result[x][y] = k
        k += 1

        # Идём вправо
        if direction == 1:
            y += 1
            if y == n - 1 - cols_filled:
                direction = 2
            continue

        # Идём вниз
        if direction == 2:
            x += 1
            if x == n - 1 - rows_filled:
                rows_filled += 1
                direction = 3
            continue

        # Идём влево
        if direction == 3:
            y -= 1
            if y == 0 + cols_filled:
                cols_filled += 1
                direction = 4
            continue

        # Идём вверх
        if direction == 4:
            x -= 1
            if x == 0 + rows_filled:
                direction = 1
            continue

    result[x][y] = k

    for i in result:
        line = ""
        for j in i:
            line += str(j) + "\t"
        print(line)

def main():
    n = int(input("Enter size >> "))
    draw_snake(n)

if __name__ == "__main__":
    main()

2 Задача:


def draw_ziggurat(n):
    size = 1
    i = 1
    while i < n:
        if size == 1:
            size = 3
        else:
            size += 2
        i += 1
    for x in range(size):
        line = ""
        for y in range(size):
            line += str(get_ring_number(x, y, size) + 1) + " "
        print(line)

def get_ring_number(x, y, n):
    x_ring = min(abs(0 - x), abs(n - x - 1))
    y_ring = min(abs(0 - y), abs(n - y - 1))
    return min(x_ring, y_ring)

def main():
    n = int(input("Enter size >> "))
    draw_ziggurat(n)

if __name__ == "__main__":
    main()
21 апреля 2020

' Написать программу, которая принимает число n и выводит таблицу размером n * n, заполненную числами от 1 до n^2 по спирали, ' выходящей из левого верхнего угла и закрученной по часовой стрелке.

    Dim intN, intX, intY, intCurN, intCor, intCorPos As Integer
    Console.Write("Введите число от 1 до 9: ")
    intN = CInt(Console.ReadLine)
    For i As Integer = 1 To intN
        Console.Write("{0,3}", i)
    Next
    intCurN = intN + 1
    intY = 1 : intX = -3 : intCor = 2
    For j As Integer = 0 To intN - 1
        For i As Integer = 0 To intN - intCor
            If intCurN > 9 Then intCorPos = -1
            Console.SetCursorPosition(Console.CursorLeft - 1 + intCorPos, Console.CursorTop + intY)
            Console.Write(intCurN)
            intCurN += 1
        Next
        For i As Integer = 0 To intN - intCor
            If intCurN > 9 Then intCorPos = -1
            Console.SetCursorPosition(Console.CursorLeft - 1 + intX + intCorPos, Console.CursorTop)
            Console.Write(intCurN)
            intCurN += 1
        Next
        intY = -intY : intX = -intX : intCor += 1
    Next
    Console.ReadKey()
21 апреля 2020

http://cpp.sh/5zupb

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  // Data definition
  const int N = 5, NN = N * N;
  int a[N][N];
  int i = 0, j = -1, di = 0, dj = 1;
  int k = N, l = k, n = 0;

  // Spiral building
  while (n++ < NN)
  {
    i += di;
    j += dj;
    a[i][j] = n;
    if (--l)
      continue;
    if (di)
      di = -di;
    else
      --k;
    swap(di, dj);
    l = k;
  }

  // Data output
  for (i = 0; i < N; ++i)
    for (j = 0; j < N; ++j)
      cout << setw(2) << a[i][j] << ((j < N - 1) ? ' ' : '\n');

  return 0;
}
21 апреля 2020

http://www.cpp.sh/2ydrz

#include <iostream>

using namespace std;

int main()
{
  // Data definition
  const int N = 5;
  int a[N][N];

  // Zikkurat building
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      a[i][j] = min(min(i, j) + 1, N - max(i, j));

  // Data output
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      std::cout << a[i][j] << ((j < N - 1) ? ' ' : '\n');

  return 0;
}
19 апреля 2020

Осторожно! Решение через геометрическое представление для второй задачи. Язык R, реализовано без применения циклов и рекурсий:

build_ziggurat <- function(n) {
  v <- c(1:(n-1), n, (n-1):1)  # пример: 1 2 3 2 1
  N <- 2*n-1

  # матрица из повторяющихся векторов
  mat1 <- matrix(v, N, N)

  # та же матрица в траспонированном ("повернутом") виде
  mat2 <- matrix(v, N, N, byrow=T)

  # смешение матриц через усреднение дает пирамиду
  # модуль разности позволяет "убрать" избыточные элементы
  # по обеим диагоналям
  print((mat1 + mat2 - abs(mat1-mat2)) /2)
}

ВАКАНСИИ

Добавить вакансию
Go-разработчик
по итогам собеседования
Backend developer (PHP / Go)
Москва, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

Подпишись

на push-уведомления