Поиск элемента по номеру строки и столбца

[Alex Fox]

svv в сообщении #1100399 писал(а):

Если такое подойдёт, могу подумать в этом направлении.

Конечно! Подойдут любые идеи.

[DeBill]

Alex Fox
это количество числе в таблице?
Ну - да, я имел ввиду количество строк.

1.Ваша задача еще напоминает классическую комбинаторную:"сколько маршрутов кратчайшей длины идет из левого нижнего угла шахматной доски в правый верхний угол?" (идем по соседним по стороне клеткам). Ответ - такой же: $C^7_{7+7}$. Потому что маршрут кодируется буквами П (вправо) и В (вверх). У Вас - то же самое: если в начале каждой строки приписать -чисто для кайфа - 0, а в конце - $m$, то символы в строке будут меняться в точности от 0 до $m$, и соответствующий маршрут на карте выглядит так: шагаем вверх (В) столько раз, на сколько отличаются символы в соседних местах вашей строки, ставим П, и т.д. Например, для строки 023 код будет такой : ПВВПВП... Опять же, эта кодировка делается совсем понятной, если вспомнить про метод "шары-перегородки" для задачи о сочетаниях с повторениями; П - это перегородки, ВВ..В - сколько шаров в соответствующем ящике. Может, эта геометрическая (или комбинаторная ))интерпретация будет вам полезна.
2. Вообше то в вашей постановке задачи , используется лексикографический порядок (а способ нумерации, предложенный svv - универсальный способ составления словаря челом, который не хочет заранее ограничивать себя количеством используемых букв ). Эта тематика - составление словарей и разработка прямого доступа к ним - наверняка классиками-программистами изучалась...
3. Аварийное завершение может происходить из-за факториалов больших чисел. Так не считайте биноминальные к-ты по этим формулам, а используйте рекуррентные (соседние бин.к-ты связаны совсем просто - получаются друг из друга домножением/делением на пару чисел) - тем более, что вам все равно нужно будет их отслеживать.

[svv]

Простите, во всех своих сообщениях выше я перепутал $m$ и $n$. Теперь постараюсь писать правильно.

Вот программка, которая выводит таблицу для заданных $m$ и $n$. Это консольное приложение на C++.

Используется синтаксис C++

//------------------------------------
#include <stdio.h>
#include <conio.h>
//------------------------------------
int fact(int n)
{
   int p=1;
   for (int i=1; i<=n; ++i)
      p*=i;
   return p;
}
//------------------------------------
int bin(int n, int k)
{
   if (k>n) return 0;
   return fact(n)/(fact(k)*fact(n-k));
}
//------------------------------------
int R(int i, int n)
{
   for (int l=0; ; ++l)
      if (bin(l+n, n)>=i) return l;
}
//------------------------------------
void GetRow(int i, int *d, int n)
{
   for (int j=n-1; j>=0; --j)
   {
      d[j]=R(i, j+1);
      i-=bin(d[j]+j, j+1);
   }
}
//------------------------------------
void main()
{
   const int
      n=4,
      m=4,
      imax=bin(n+m, n);

   for (int i=1; i<=imax; ++i)
   {
      int d[n];

      GetRow(i, d, n);
      for (int j=0; j<n; ++j)
         printf("%2d", d[j]);

      printf("\n");
   }
   getch();
}
//------------------------------------
 

Таблица выводится в моём порядке. Чтобы выводилась в Вашем, надо три оператора в основном цикле функции main (Вы увидите, какие) заменить на

Используется синтаксис C++

      GetRow(imax-i+1, d, n);
      for (int j=0; j<n; ++j)
         printf("%2d", m-d[n-1-j]);

Изменение сведётся к обращению порядка столбцов, строк и замены каждого числа $d$ на $m-d$.

Программа выводит таблицу построчно, но каждая строка вычисляется независимо от остальных, исходя только из её номера (ну, и констант $m, n$), в этом «честность» программы. Вкратце о том, что делает каждая функция.
fact(n) вычисляет $n!$
bin(n, k) вычисляет $C_n^k$
R(i, n), самая страшная функция. Для данных $i, n$ находит минимальное целое положительное $\ell$, такое, что $C_{n+\ell}^n\geqslant i$.
GetRow(i, d, n) вычисляет для данного номера строки $i$ все её элементы $d_{ij}$, где $j=0..n-1$
Аргументы функций предполагаются целыми неотрицательными.
Если Вы замените реализации функций более эффективными, я буду только рад.

[Alex Fox]

#include<iostream>
using namespace std;

int fact(int x)
{
    int m=1;
    for(int i(1); i <= x; i++)
{
    m *= i;
}
    return m;
}
int C(int x, int y)
{
    int z = fact(x+y)/(fact(x)*fact(y));
    return z;
}
int main()
{
    setlocale(LC_ALL, "Rus");
    int n, m, rowNumber, columnNumber;
    cout << "Введите число cтолбцов:\t\t";
    cin >> n;
    cout << "Введите количество значений:\t";
    cin >> m;
    cout << "Укажите строку:\t\t\t";
    cin >> rowNumber;
    cout << "Укажите столбец:\t\t";
    cin >> columnNumber;
    int k=0;

    for(;;)
    {
        if(rowNumber<=C(n-1,m))
        {
            cout << k;
            n--;
        }
        else if(rowNumber>C(n-1,m))
        {
           rowNumber -=C (n-1,m);
           k++;
           m--;
           continue;
        }
        if(n==0)
            break;
    }
    return 0;
}

Вот мой код, сразу скажу, что я не программист, поэтому это далеко не самая эффективная реализация алгоритма. Проверял его для некоторых, небольших, частных значений. Как верно заметил DeBill краши вероятнее всего из-за биномиальных коэфф-в.

[svv]

Ваша программа красивая и многообещающая, но у меня она пока не заработала. Я переписал её так, чтобы она выдавала всю таблицу для заданных $m, n$. Сейчас в каждой строке повторяется одно и то же число. Это потому, что в Вашем алгоритме пока что никак не используется columnNumber. Что надо исправить?

[Alex Fox]

svv в сообщении #1100495 писал(а):

Ваша программа красивая и многообещающая, но у меня она пока не заработала.

Странно, у меня работает. columnNumber действительно никак не используется, я планировал потом дописать программу, чтобы на экран вместо всей строки выводился искомый элемент, тут то и понадобилась бы эта переменная, но поскольку программа падает если выставлять значения переменных больше 20, то я не стал замарачиваться.
UPD: Возможно у вас не работает из-за метода setlocale

[svv]

Ура, всё заработало!

[arseniiv]

Честно говоря, стоило бы переписать функцию, выдающую $C_n^m$. Она ведь могла бы выдавать правильные значения намного чаще, если реализовать её как $\prod_{i = 1}^{m_1} (m_2 + i)/i$; $m_1 = \min\{m,n-m\}$, $m_2 = \max\{m,n-m\}$.