Дискретная математика

[sinenki]

Здравствуйте!!!! Учусь на 2 курсе... Задали задачку... Ничего в ней не понял.. НЕ решение грозит вылетом, препод принципиальный=(((

Разработать на языке Pascal программу для решения следующей задачи. Предоставить список тестов. Продемонстрировать работоспособность программы на компьютере.
Задача
Построить все отображения множества {1,...k} в {1,...,n} предполагается что {k<=n}, такие что ни один элемент не переходит сам в себя. Порождение очередного элемента должно требовать порядка k действий

Заранее спасибо!!!

[PAV]

Тема переносится в раздел Программирование.

В условии ошибка, ибо k нигде не фигурирует.

[Xaositect]

А где здесь $k$ вообще? Или отображения все-таки из $\{1,\dots,k\}$ в $\{1,\dots,n\}$?

Ваша задача сводится к перечислению элементов множества $M_1\times M_2 \times \dots \times M_k$, где $M_i = \{x| 1\leq x \leq n, x\neq i\} = \{1,\dots,i-1,i+1,\dots n\}$

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

[sinenki]

ДА, я ошибся, действительно вот так правильно Построить все отображения множества {1,...k} в {1,...,n} предполагается что {k<=n}, такие что ни один элемент не переходит сам в себя. Порождение очередного элемента должно требовать порядка k действий

[Xaositect]

Pascal я уже не помню, вот код на C (сделан на скорую руку, может содержать ошибки)

#include <stdio.h>                  

#define K 4
#define N 7
//(например)

int a[K];

void first(int *a)
{                 
    for(int i = 0; i<K; i++)
    {                       
        a[i] = 0;           
    }                       
    a[0] = 1;               
}                           

int nextat(int *a, int i)
{                        
    if(i<0)              
    {                    
        return 0;        
    }                    
    a[i]++;              
    if (a[i] == N)       
    {                    
        a[i] = 0;        
        nextat(a, i-1);
    }
    return 1;
}

int next(int* a)
{
    return nextat(a, K-1);
}

void print(int *a)
{
    for(int i = 0; i<K; i++)
    {
        printf("%d->%d ", i+1, a[i]+1);
    }
    printf("\n");
}

int main()
{
    first(a);
    print(a);
    while(next(a))
    {
        print(a);
    }
}

[sinenki]

спасибо, сча попробую переделать в паскале=)

[PAV]

Xaositect
напоминаю, что выкладывание готовых решений для учебных задач (в том числе - готовых программ) нарушает правила и традиции форума. Лучше было бы объяснить автору вопроса словами общую суть алгоритма и дать возможность закодировать его самому...

[Xaositect]

Я, кстати, забыл туда вставить основную проверку (${\tt a[i]!=i}$)
Это код перечисления всех функций.

[sinenki]

а куда там встаить основную проверку, а то оно как-то зациклилось????

[Xaositect]

Ну, во-первых, в рекурсивной функции надо вместо nextat(a, i-1); поставить return nextat(a, i-1);
Тогда не будет циклиться.
А основную проверку при увеличении элемента, если равен i, то еще раз увеличить.

[PAV]

Вот видите, автор вопроса механически переписал Ваше решение, но что там к чему, что делает каждый блок - не понимает. Разве это называется обучением?

[Xaositect]

Код показывает основную идею(генерация функций в лексикографическом порядке)
Я сразу предупредил, что код ошибочен.
Надо было еще сразу предупредить, что легче написать свой код, чем отдебажить чужой.

Можно еще к Кнуту отослать (том 4, часть 2, уже есть на русском)