Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
#pragma
Временно недоступен
955 / 226 / 14
Регистрация: 12.04.2009
Сообщений: 921
#1

Написать функцию, которая найдёт возможный вариант размещения жителей племени - C (СИ)

08.09.2012, 17:21. Просмотров 1188. Ответов 11
Метки нет (Все метки)

Есть такая интересная задачка, давалась в одном из вузов на экзамене в первом семестре.
Текст задачи
На острове живут N человек племени Тумба-Юмба, и между ними со временем возникли социальные неравенства. Чтобы отделить людей одного статуса от другого, они построили k домов. Только жители одного социального статуса могут жить в одном доме. И им предстоит решить, кто где будет жить, учитывая статус, и возможно ли разместить всех в домах в данной ситуации.

Написать функцию, которая найдёт возможный вариант размещения жителей. Входные данные для функции - количество домов k, максимальное количество жителей в каждом доме m, и матрица a[N][N] (N - определён как #define), которая показывает, кто может жить с кем: a[i][j] содержит 1, если житель i может жить с жителем j, и 0, если не может. Обратите внимание, что матрица симметрична (если a[i][j] == 1, то и a[j][i] == 1).

Функция должна определить любое возможное размещение жителей или сообщить об ошибке. Если размещение возможно, функция вернёт 1 и запишет размещение в массив h[] длиной N, где h[i] содержит номер дома, к которому относится житель (номера домов от 0 до k), если размещение невозможно, функция возвращает 0 и содержание массива h[] не важно.

Ограничения и замечания:

1) Функция должна быть рекурсивной и использовать алгоритм поиска с возвратом http://en.wikipedia.org/wiki/Backtracking

2) Нельзя использовать статические переменные

3) Необходимо сделать проверку, чтобы рекурсивная функция не вызывалась лишний раз, когда у задачи нет решения.

4) Чтобы упростить код, можно сделать вспомогательную функцию (можно, чтобы она была рекурсивной)

5) Определение главной функции выглядит так:
C
1
2
3
4
int housing (int a[N][N], int k, int m, int h[]) {
   ...
   ...
}
Заполните её кодом, чтобы всё работало
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2012, 17:21
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Написать функцию, которая найдёт возможный вариант размещения жителей племени (C (СИ)):

Найти вариант размещения на столе наибольшего количества костей
Имеются стол прямоугольной формы с размерами a×b (a и b – целые числа, a > b) и...

Написать функцию, которая которая удаляет из массива элемент с заданным индексом
Было дано задание написать функцию, которая которая удаляет из массива элемент...

Написать функцию, которая табулирует любую указанную функцию
Задача дословно звучит так: Написать функцию, которая табулирует любую...

Решение системы уравнений: написать функцию, которая как параметр будет использовать другую функцию
Ребята помогите разобраться с указателем на функцию! у меня решается система...

Написать функцию, которая упорядочивает массив целых чисел или по возрастанию или по убыванию. Использовать эту функцию
Написать функцию, которая упорядочивает массив целых чисел или по возрастанию...

Написать функцию, которая вычисляет значение a^b
Написать функцию, которая вычисляет значение а^б. Числа а и б могут быть...

11
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
09.09.2012, 08:26 #2
Цитата Сообщение от #pragma Посмотреть сообщение
Есть такая интересная задачка, давалась в одном из вузов на экзамене в первом семестре.
Мутноватое условие:
Вот матрица a[3][3]:
010
101
010
Если рассмаривать эти строки:
Цитата Сообщение от #pragma Посмотреть сообщение
a[i][j] содержит 1, если житель i может жить с жителем j, и 0, если не может.
Получается что 1-ый и 3-ий жить в одном доме не могут.

А если рассматривать эти строки:
Цитата Сообщение от #pragma Посмотреть сообщение
Только жители одного социального статуса могут жить в одном доме.
то получается, что у 1-го статус такой же как и у 2-го. У 2-го статус такой же как и у 3-его. Соответственно у 1-го и 3-его тоже одинаковые статусы, и они в одном доме жить могут.
0
#pragma
Временно недоступен
955 / 226 / 14
Регистрация: 12.04.2009
Сообщений: 921
09.09.2012, 10:10  [ТС] #3
Имелось в виду, что статус - обязательное условие для сожительства, но не достаточное (они могут не уживаться вместе). Это могли быть специально даны такие данные, чтобы запутать. Главное - это нули и единицы.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
09.09.2012, 14:18 #4
Цитата Сообщение от #pragma Посмотреть сообщение
Имелось в виду, что статус - обязательное условие для сожительства, но не достаточное (они могут не уживаться вместе). Это могли быть специально даны такие данные, чтобы запутать. Главное - это нули и единицы.
хорошо, просто ответьте: для приведенного мною примера все трое могут жить в одном доме или максимум в одном доме только двое, а третий в другом доме?

Кстати вот это условие:
Цитата Сообщение от #pragma Посмотреть сообщение
5) Определение главной функции выглядит так:
C
1
2
3
4
int housing (int a[N][N], int k, int m, int h[]) {
 ...
 ...
}
сразу направляет на не очень рациональное решение (если есть желание могу объяснить почему).
В общем могу решить эту задачу, но своим способом (более подходящим для этой задачи).
0
#pragma
Временно недоступен
955 / 226 / 14
Регистрация: 12.04.2009
Сообщений: 921
09.09.2012, 14:58  [ТС] #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
хорошо, просто ответьте: для приведенного мною примера все трое могут жить в одном доме или максимум в одном доме только двое, а третий в другом доме?
Максимум в одном доме только двое. Кстати, диагональ a[2][2] ... вся должна быть заполнена единицами, иначе это случай неправильного ввода .

Цитата Сообщение от valeriikozlov Посмотреть сообщение
Кстати вот это условие:
сразу направляет на не очень рациональное решение (если есть желание могу объяснить почему).
В общем могу решить эту задачу, но своим способом (более подходящим для этой задачи).
Да, объясните почему наталкивает на не очень рациональное решение, интересно. Причём прототип функции уже дан, его нельзя менять, но можно писать вспомогательную функцию. Такой , видимо, экзамен, наталкивающий на ошибки
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
09.09.2012, 18:00 #6
Цитата Сообщение от #pragma Посмотреть сообщение
Да, объясните почему наталкивает на не очень рациональное решение, интересно. Причём прототип функции уже дан, его нельзя менять, но можно писать вспомогательную функцию.
Тогда еще раз читаем:

Цитата Сообщение от #pragma Посмотреть сообщение
1) Функция должна быть рекурсивной
Цитата Сообщение от #pragma Посмотреть сообщение
5) Определение главной функции выглядит так:
C
1
2
3
4
int housing (int a[N][N], int k, int m, int h[]) {
 ...
 ...
}
При очередном вызове функции housing() мы не знаем, сколько жителей заселено уже в дома (т.е. не знаем пора ли заканчивать вызовы рек функции, вполне возможно, что все жители уже расселены). Да согласен, можно например до первого вызова заполнить h[] значениями -1 и при очередном вызове housing() просмотривать массив h[]: есть ли еще значения -1 в массиве h[] ( если есть, то значит не все жители расселены).
Но проще добавить в определение функции еще один параметр.

И еще:
При очередном вызове функции housing() мы не знаем, сколько домов заполнено (может быть они уже все заполнены и пора делать возвращение на предыдущий вызов housing() ).
В принципе тоже можно это дело вычислить по данным h[]. Но проще добавить еще один параметр в housing() : номер очередного свободного дома.
Хотя можно для решения этой проблемы уменьшать k при очередном вызове housing()
1
#pragma
Временно недоступен
955 / 226 / 14
Регистрация: 12.04.2009
Сообщений: 921
09.09.2012, 18:04  [ТС] #7
Постановка задачи в принципе предполагает определение новой рекурсивной функции с какими угодно параметрами, и тоже рекурсивной.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
09.09.2012, 18:23 #8
Цитата Сообщение от #pragma Посмотреть сообщение
Постановка задачи в принципе предполагает определение новой рекурсивной функции с какими угодно параметрами, и тоже рекурсивной.
Согласен, но я сейчас писал именно о первой функции: она обязательно рекурсивная и проблемы описанные мною именно для ее вызовов.
1
#pragma
Временно недоступен
955 / 226 / 14
Регистрация: 12.04.2009
Сообщений: 921
10.09.2012, 02:17  [ТС] #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Согласен, но я сейчас писал именно о первой функции: она обязательно рекурсивная и проблемы описанные мною именно для ее вызовов.
Как раз она не обязательно рекурсивная.

Добавлено через 6 часов 50 минут
Я согласен, есть тут некая двусмысленность, но в-общем имеется в виду следующее: если главная функция не рекурсивная, то рекурсивной должна быть вспомогательная функция, или, если главная рекурсивная, то вспомогательная не обязательно рекурсивная. (вспомогательной функции может и не быть)
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2012, 06:50 #10
должно работать, но сам алгоритм я бы не сказал что самый эффективный:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void rec(int a[N][N],int m,int h[],int num, int k, int M)
{
    for(i=0; i<N; i++)
        if(h[i]==-1)
            break;
    if(i==N)
        return 1;
    if(housing (a, k-1, M, h)==1)
        return 1;
    int i,j, fl;
    if(m==0)
        return 0;
    for(i=0; i<N; i++)
        if(h[i]==-1)
        {
            fl=1;
            for(j=0; j<N; j++)
                if(h[j]==k && a[num][j]==0)
                    fl=0;
            if(fl)
            {
                h[i]=k;
                if(rec(a, m-1, h, num, k, M)==1)
                    return 1;
                h[i]=-1;
            }           
        }
}
 
int housing (int a[N][N], int k, int m, int h[]) {
   int i,j;
   if(k==0)
   {
       for(i=0; i<N; i++)
           if(h[i]==-1)
               break;
        if(i==N)
            return 1;
       return 0;
   }
   for(i=0; i<N; i++)
       if(h[i]==-1)
       {
           h[i]=k;
           if(rec(a, m-1, h, i, k, m)==1)
               return 1;
           h[i]=-1;
       }
   return 0;
}
до первого вызова housing() массив h[] нужно заполнить значениями -1.
1
#pragma
Временно недоступен
955 / 226 / 14
Регистрация: 12.04.2009
Сообщений: 921
11.09.2012, 09:41  [ТС] #11
Вариант решения от экзаменаторов
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int housing ( int a[N][N], int k, int m, int h[] ) {
   return housing_aux(a,k,m,h,0);
}
 
int housing_aux (int int a[N][N], int k, int m, int h[], int p) {
 
   int house, i, count;
   if (N == p) return 1;
   
   for (house = 0; house < k; house++) {
      count  = 0;
      for (i = 0; i < p; i++) {
         if (h[i] == house) {
            if (!a[p][i]) {
               count = m;
               break;
            }
            count++;
         }
      }
      if (count >= m) continue;
      h[p] = house;
      if (housing_aux (a, k, m, h, p+1)) 
         return 1;
   }
   return 0;
}
0
zitxbit
89 / 741 / 279
Регистрация: 11.04.2012
Сообщений: 971
11.09.2012, 11:59 #12
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <memory.h>
 
#define N 50
 
const int m = 5;  // number of persons in a single house
const int s = 12; // number of houses
 
int g_house = 1, d = 0;
 
void init_tree(int** tree)
{
    for (int i = 0; i < N; i++)
    {
        int j = 0; tree[i] = new int[N];
        while (j < N) tree[i][j++] = (j > i) ? 1 : 0;
    }
}
 
void gen_entities(int* ent)
{
    for (int i = 0; i < N; i++)
        ent[i] = rand() % 2;
}
 
void invert_entities(int* ent, int* r_ent, int count)
{
    for (int i = 0; i < count; i++)
        r_ent[i] = ent[i] == 0 ? 1 : 0;
}
 
int find_root(int* ent)
{
    int i = 0; while (ent[i] == 0) i++;
    return i;
}
 
bool is_visited(int* p, int top, int count)
{
    for (int i = 0; i < count; i++)
         if (p[i] == top) return true;
    return false;
}
 
void housing(int** tree, int* entities, int* houses, int* visited, int r)
{
    int w = 0, count = w;
    int nh = count = houses[r] = 
        (houses[r] == 0) ? g_house : houses[r]; 
    
    if (is_visited(visited, r, d)) return;
 
    int matched[N] = { 0 }; visited[d++] = r;
    for (int index = 0; index < N; index++)
        if (entities[r] == entities[index] && tree[r][index])
        {
            matched[w++] = index;
 
            if (count >= m) { count = 0; nh++; }
            houses[index] = (houses[index] == 0) ? nh : houses[index];
 
            tree[r][index] = 0; count++; 
        }
 
    for (int nindex = 0; matched[nindex] > 0; nindex++)
        housing(tree, entities, houses, visited, matched[nindex]);
 
    g_house = nh;
}
 
int main()
{ 
    g_house = 1;
 
    int*  p = new int[N];  gen_entities(p);
    int** a = new int*[N]; init_tree(a);
 
    int *h = new int[N], *v = new int[N];
    memset((void*)h, 0x00, sizeof(int) * N);
    memset((void*)v, 0x00, sizeof(int) * N);
 
    housing(a,p,h,v,0);
 
    int* inv_p = new int[N]; invert_entities(p, inv_p, N);
    int r = find_root(inv_p);
 
    memset((void*)v, 0x00, sizeof(int) * N);
 
    housing(a,inv_p,h,v,r);
    
    for (int m = 0; m < N; m++)
        printf("%d ",h[m]);
    printf("\n");
 
    _getch();
 
    return 0;
}
http://liveworkspace.org/code/6491423899c0bc76427c37f7d4157e3b
2
Миниатюры
Написать функцию, которая найдёт возможный вариант размещения жителей племени  
11.09.2012, 11:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.09.2012, 11:59
Привет! Вот еще темы с решениями:

Написать функцию, которая возводит а в степень b
Помогите пожалуйста решить. Написать функцию, которая возводит а в степень b.

Написать функцию, которая вычисляет значение а*b
Написать функцию, которая вычисляет значение а*b. Числа а и b могут быть любыми...

Написать функцию, которая вычисляет объем цилиндра
Написать функцию, которая вычисляет объем цилиндра. Параметрами функции должны...

Написать функцию, которая возводит число в степень
1. написать функцию которая принимает число и степень в которую возвести число


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru