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

Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

1 3 6 10
2 5 9 13
4 8 12 15
7 11 14 16

Размерность произвольная.
У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

Здравствуйте, Yadosupp, Вы писали:

Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

Подсказка: площадь треугольника.

Здравствуйте, sergey_shandar, Вы писали:

_>Здравствуйте, Yadosupp, Вы писали:

Y>> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

_>Подсказка: площадь треугольника.

А чуть конкретнее? Не догоняю после ночной смены

Здравствуйте, Yadosupp, Вы писали:

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

Y>Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.

int f( int N, int x, int y )
{
    int d = x + y;           // номер диагонали
    int a = ((d+1) * d) / 2; // кол-во ячеек выше диагонали
    int n = a + x;           // значение в ячейке при условии бесконечной матрицы

    // считаем количество ячеек, отрезанных от бесконечной матрицы
    // нижней границей нашей матрицы и диагональю, 
    // на которой расположена текущая ячейка
    // (сама диагональ входит)
    int d1 = (d+1) > N ? (d+1) - N : 0;  // номер диагонали в отрезаемой матрице
    int a1 = ((d1+1) * d1) / 2;          // количество ячеек

    // считаем количество ячеек, отрезанных от бесконечной матрицы
    // правой границей нашей матрицы и диагональю,
    // на которой расположена текущая ячейка
    int d2 = d > N ? d - N : 0;          // номер диагонали в отрезаемой матрице
    int a2 = ((d2+1) * d2) / 2;          // количество ячеек

    return n - a1 - a2;  // соб-но результат
}

Здравствуйте, Demon, Вы писали:

D>Здравствуйте, Yadosupp, Вы писали:

Y>>Как-то я встретил задачку, ответ на которую ищу до сих пор. Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.
D>Чего-то долго.

Да не мне преподавали

D>

D>int f( int N, int x, int y )
D>{
 [пропущено]
D>}
D>

Логика ясна. Но нужно заполнять циклами

Здравствуйте, Yadosupp, Вы писали:

Y>Как-то я встретил задачку, ответ на которую ищу до сих пор. Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.

Y>Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.
Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

const N = 4;
int array [N][N];

for (int i=0, k=0; i<N; i++)
    for (int j=i; j>=0; j++)
        array [i-j][j] = k++;

Здравствуйте, Yadosupp, Вы писали:

На C#:

using System;
using System.Collections.Generic;
using System.Text;

namespace SquadreFill
{
    class Program
    {
        const int n = 4;

        static void Main(string[] args)
        {
            int[,] square = new int[n, n];

            int value = 1;
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < i + 1; j++, value++)
                {
                    square[i - j, j] = value;
                }
            }
            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j < n-i; j++, value++)
                {
                    square[n - j - 1, i + j] = value;
                }
            }

            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    Console.Write(square[i, j]);
                    Console.Write("\t");
                }
                Console.Write("\n");
            }
        }
    }
}

Здравствуйте, Yadosupp, Вы писали:

Y> Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.

То есть, чисто императивный подход. Тогда итерировать по диагоналям.

template<class SomeSquare>
void hatch_fill(SomeSquare& square, int size)
{
    int diag, elem; // номер диагонали и элемента на диагонали
    int current = 1;
    for(diag = 0; diag < size; ++diag) // расширение... 0 это верхний левый угол
        for(elem = 0; elem <= diag; ++elem) // диагональ #diag содержит diag+1 элемент
            square[elem][diag-elem] = current++;
    for(diag = size-1; diag >= 0; --diag) // сжатие... 0 это нижний правый угол
        for(elem = 0; elem <= diag; ++elem)
            square[size-1-diag+elem][size-1-elem] = current++;
}

Y> 1  3  6 10
Y> 2  5  9 13
Y> 4  8 12 15
Y> 7 11 14 16

Можно и функцию написать...

int triangle_count(int h) { return h*(h+1)/2; }

int hatch_value(int x, int y, int s)
{
    int h = x+y;
    if(h < s)
        return 1 + triangle_count(h) + x;
    else
        return s*s - triangle_count(s*2-1-h) + x-(h-s);
}

Здравствуйте, Yadosupp, Вы писали:

Y>Как-то я встретил задачку, ответ на которую ищу до сих пор. Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.

Y>Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.
Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

Вот, "в лоб"

//int k = 4;
//int quad[4][4];

int n = 1;
for(int i = 0; i < k*2 - 1; ++i)
    for(int c = 0; c <= min(i, k-1); ++c)
        for(int r = min(i, k-1); r >= 0; --r)
            quad[c][r] = n++;

1 3 6 10
2 5 9 13
4 8 12 15
7 11 14 16

Здравствуйте, Yadosupp, Вы писали:

Y>Как-то я встретил задачку, ответ на которую ищу до сих пор. Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.

Y>Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.
Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

        int N = 5;
        int[][] array = (int[][]) Array.newInstance(Integer.TYPE, new int[]{N, N});

        int k = 1;
        for (int sum = 0; sum < 2 * N - 1; sum++)
        {
            int max = sum;
            int min = 0;
            if (sum >= N)
            {
                max = N - 1;
                min = sum - N + 1;
            }
            for (int i = max; i >= min; i--)
            {
                array[i][sum - i] = k++;
            }
        }

        for (int i = 0; i < array.length; i++)
        {
            System.out.println(Arrays.toString(array[i]));
        }

Здравствуйте, Yadosupp, Вы писали:

Y>Как-то я встретил задачку, ответ на которую ищу до сих пор. Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.

Y>Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.
Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

pure C неоптимизированный

int ** f(int N)
{
int ** arr = (int **)malloc(sizeof(int*)*N);
bzero(arr, sizeof(int*)*N);
int i, j, k, cnt=0;
for (i=0;i<(N<<1)-1;i++)
{
if (i<N && !arr[i]) arr[i] = (int *)malloc(sizeof(int)*N);
for (j=(i<N)?i:N-1,k=(i<N)?0:i-N+1;((j>=0)&&(k<N));j--,k++)
{
arr[j][k] = ++cnt;
}
}
for (i=0;i<N;i++)
{
for (j=0;j<N;j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return arr;
}

f(4);

1 3 6 10
2 5 9 13
4 8 12 15
7 11 14 16

f(6);

1 3 6 10 15 21
2 5 9 14 20 26
4 8 13 19 25 30
7 12 18 24 29 33
11 17 23 28 32 35
16 22 27 31 34 36

Здравствуйте, Yadosupp, Вы писали:

Y>Как-то я встретил задачку, ответ на которую ищу до сих пор. Задачка предлагалась ученикам, которые на тот момент кроме циклов практически ничего и не знали.

Y>Итак, суть задачки — автоматом заполнить квадрат заданной размерности следующим образом

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.
Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог :shuffle:

    const int N(4);
    int a[N][N];

    for(int i = 0, n = 1; i < N*2-1; i++)
        for
        (
            int c = i < N ? 0 : i - N + 1, 
                r = i < N ? i : N - 1;
            r >= 0 &&
            c < N; 
            c++, 
            r--
        )
            a[c][r] = n++;

    // print matrix
    {
        for(int y(0); y<N; y++)
        {
            for(int x(0); x<N; x++)
                printf("%02d ", a[x][y]);
            printf("\n");
        }
    }

Yes !!! :super:

Здравствуйте, KickMaster, Вы писали:

KM>

KM>    const int N(4);
KM>    int a[N][N];

KM>    for(int i = 0, n = 1; i < N*2-1; i++)
KM>        for
KM>        (
KM>            int c = i < N ? 0 : i - N + 1, 
KM>                r = i < N ? i : N - 1;
KM>            r >= 0 &&
KM>            c < N; 
KM>            c++, 
KM>            r--
KM>        )
KM>            a[c][r] = n++;

KM>    // print matrix
KM>    {
KM>        for(int y(0); y<N; y++)
KM>        {
KM>            for(int x(0); x<N; x++)
KM>                printf("%02d ", a[x][y]);
KM>            printf("\n");
KM>        }
KM>    }
KM>

KM>Yes !!!

Понятно, что супер. А еще какое решение есть?

Здравствуйте, Yadosupp, Вы писали:

Y>Понятно, что супер. А еще какое решение есть?

Тут есть 4 решения:
— построить последовательность (x,y)[k], k=1..N^2, возможно рекуррентную, т.е. функцию (x,y)[k] = F(k,(x,y)[k-1]) — и оббежать квадрат по ней, заполняя ячейки
— найти аналитическое решение этой функции (x,y)[k] = F(k) и сделать то же самое
— построить последовательность k[x,y] для построчной развёртки — возможно, рекуррентную — и, построчно оббегая квадрат, вывести найденные значения
— найти аналитическое решение k = F(x,y) — и, опять же, построчно развернуть

Первое и четвёртое решения уже найдены. Третье сводится к четвёртому и поэтому интереса не представляет.
Осталось найти второе. (x,y) = F(k).

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Yadosupp, Вы писали:

К>Тут есть 4 решения:
К>- построить последовательность (x,y)[k], k=1..N^2, возможно рекуррентную, т.е. функцию (x,y)[k] = F(k,(x,y)[k-1]) — и оббежать квадрат по ней, заполняя ячейки
К>- найти аналитическое решение этой функции (x,y)[k] = F(k) и сделать то же самое
К>- построить последовательность k[x,y] для построчной развёртки — возможно, рекуррентную — и, построчно оббегая квадрат, вывести найденные значения
К>- найти аналитическое решение k = F(x,y) — и, опять же, построчно развернуть

К>Первое и четвёртое решения уже найдены. Третье сводится к четвёртому и поэтому интереса не представляет.
К>Осталось найти второе. (x,y) = F(k).

Даже не знал, что так много всего. И почему я в свое время увлекался биологией?

А подобная функциональная зависимость есть?

Здравствуйте, Yadosupp, Вы писали:

К>>Осталось найти второе. (x,y) = F(k).

Y>Даже не знал, что так много всего. И почему я в свое время увлекался биологией?

Y>А подобная функциональная зависимость есть?

А как же. Конечно, есть. Ведь каждому числу k из [1..n^2] соответствует уникальная пара (x,y) куда это число помещено.

Сперва, как истинные программисты, перейдём к отсчёту с нуля. t = k-1.

Площадь (количество ячеек) треугольника с катетом m равна s(m) = 1+2+...+m = m*(m-1)/2
Обратная функция — m(s) — это положительный корень квадратного уравнения.
m(s) = (sqrt(8s+1)-1)/2

Если 0 <= t < s(n), то ячейка принадлежит верхне-левой половине квадрата.
Найдём
m0 = floor m(t) — катет полного треугольника, за пределами которого находится ячейка.
s0 = s(m0) — его площадь
t0 = t-s0 — номер в диагонали

(x,y) = (t0, m0-t0) — опять же, нумерация координат с нуля.

А если t <= s(n) < n^2, то отзеркалим
t' = n^2-1-t
(x',y') находим по предыдущей формуле
(x,y) = (n-1-x',n-1-y')

Кажется, так.

Здравствуйте, Кодт, Вы писали:

К>А как же. Конечно, есть. Ведь каждому числу k из [1..n^2] соответствует уникальная пара (x,y) куда это число помещено.

Радует

К>Сперва, как истинные программисты, перейдём к отсчёту с нуля. t = k-1.

А как из всего этого сделать прогу на Паскале? Или хотя бы на Си, перевести не проблема. А то я окончательно запутался

Здравствуйте, Yadosupp, Вы писали:

Y>А как из всего этого сделать прогу на Паскале? Или хотя бы на Си, перевести не проблема. А то я окончательно запутался

Умеешь строить 2-мерные массивы произвольной размерности? Если нет, сперва научись этому делу.

/* допустим, у нас есть абстрактный API работы с квадратами */

typedef struct tagSquare *HSquare; /* хэндл двумерного массива */

HSquare new_square(int n);
void delete_square(HSquare sq);
int square_size(HSquare sq);

typedef struct tagXY { int x, y; } XY;
inline XY xy(int x, int y) { XY at = {x,y}; return at; }

int square_get(HSquare sq, XY at);
void square_set(HSquare sq, XY at, int value);

/* а теперь пишем наши функции */
XY xy_by_num(int n, int k) { ..... }
int num_by_xy(int n, XY at) { ..... }

void fill_square_by_num(int n)
{
    HSquare sq = new_square(n);
    int k, nn;
    XY at;
    
    for(k=0, nn=n*n; k!=nn; ++k)
        square_set(sq, xy_by_num(n,k), k);

    for(at.y=0; at.y!=n; ++at.y)
    {
        for(at.x=0; at.x!=n; ++at.x)
        {
            printf(" %3d", square_get(sq,at));
        }
        printf("\n");
    }

    delete_square(sq);
}


void fill_square_by_lines(int n)
{
    /* тут даже не надо создавать массив... но если очень хочется, то можно */
    HSquare sq = new_square(n);
    XY at;
    int k;

    for(at.y=0; at.y!=n; ++at.y)
    {
        for(at.x=0; at.x!=n; ++at.x)
        {
            k = num_by_xy(at);
            printf(" %3d", k); /* сразу и заполняем, и выводим */
            square_set(sq, at, k);
        }
        printf("\n");
    }
    
    delete_square(sq);
}

(Специально недо-ответил на твой вопрос, чтобы ты поупражнялся в кодировании).

Здравствуйте, Yadosupp, Вы писали:

Y> 1 3 6 10
Y> 2 5 9 13
Y> 4 8 12 15
Y> 7 11 14 16

Y> Размерность произвольная.
Y> У кого какие мнения? Ясно, что нужно каждое следующее значение рассчитывать из положения в квадрате и размерности, но по какой формуле? Я вывести не смог

Надо найти зависимость, Ux уже привёл расширенный массим по этой зависимости:

 1  3  6 10 15 21 
 2  5  9 14 20 26 
 4  8 13 19 25 30 
 7 12 18 24 29 33 
11 17 23 28 32 35 
16 22 27 31 34 36

Суть сводиться, к тому, что:
1.Есть матрица MxM (М на М)
2.Строим левый крайний столбец так:

|| [ 1]
|| +1
|| [ 2]
|| +2
|| [ 4]
|| +3
|| [ 7]
|| +4
|| [11]
|| +(M-1)
\/ [16]

2.Строим нижнюю крайнюю строчку так:

[16] +M [22]  +5 [27]  +4 [31]  +3 [34]  +2 [36]
----------------------------------------------->

3.А дальше всё просто, каждыя (i,j) элемент (считая слева направо/сверху вниз) это елемент (i-1,j+1)+1:

[ 1]    [ 3]
      +1
    /
[ 2]    [ 5]
      +1
    /
[ 4]    [ 8]
      +1
    /
[ 7]

По такой зависимоти можно любых по-вкусу алгоритмов нагенерить

Здравствуйте, Vain, Вы писали:

V>Надо найти зависимость, Ux уже привёл расширенный массим по этой зависимости:
[skipped]
V>По такой зависимоти можно любых по-вкусу алгоритмов нагенерить

То, что нужно. Безо всякой математической ереси. Спасибо