2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Дискретная математика
Сообщение17.05.2009, 16:47 
Аватара пользователя
Тема переносится в раздел Программирование.

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

 
 
 
 Re: Дискретная математика
Сообщение17.05.2009, 16:55 
Аватара пользователя
А где здесь $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\}$

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

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

 
 
 
 Re: Дискретная математика
Сообщение17.05.2009, 17:33 
Аватара пользователя
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);
    }
}

 
 
 
 Re: Дискретная математика
Сообщение17.05.2009, 17:40 
спасибо, сча попробую переделать в паскале=)

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

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

 
 
 
 Re: Дискретная математика
Сообщение17.05.2009, 17:58 
а куда там встаить основную проверку, а то оно как-то зациклилось????

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

 
 
 
 Re: Дискретная математика
Сообщение17.05.2009, 18:05 
Аватара пользователя
Вот видите, автор вопроса механически переписал Ваше решение, но что там к чему, что делает каждый блок - не понимает. Разве это называется обучением?

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

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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group