VPF::[C]подмножества - Форум программистов

Wolandello

Дата 31.10.2009, 20:59 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 12
Регистрация: 17.5.2009
Где: Ukraine

Репутация: нет
Всего: нет

Задано натуральное число n, определить и вывести на экран (по одному разу) все подмножества множества 1 .. n
с заданной суммой S (числа в каждом подмножеству повторяться не могут)
Народ подскажите решение

t_gran

Дата 2.11.2009, 07:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Ну-у-у..., как то так!:

Код


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Само множество
struct TSet
{
   int data;
   struct TSet *next;
};

//----------------------------------------------//
// Добавление во множество. Если указанный элемент уже существует,
// то добавления не происходит
int QuantityAdd (struct TSet **theSet, int theData)
{
   int isAdd= 0;
   if (!(*theSet))
   {
      *theSet= malloc(sizeof(struct TSet));
      (*theSet)->data= theData;
      (*theSet)->next= 0;
      isAdd++;
   }
   else
   {
      struct TSet *pSet= *theSet;
      while (pSet->next)
      {
         if (pSet->data == theData)
            break;
         pSet= pSet->next;
      }
      if (pSet->data != theData)
      {
         struct TSet *node= malloc(sizeof(struct TSet));
         node->data= theData;
         node->next= 0;
         pSet->next= node;
         isAdd++;
      }
   }
   return isAdd;
}
//----------------------------------------------//
// Очистка множества
void QuantityDel (struct TSet **theSet)
{
   struct TSet *node;
   while (*theSet)
   {
      node= *theSet;
      *theSet= (*theSet)->next;
      free(node);
   }
   *theSet= 0;
}
//----------------------------------------------//
// Получение суммы элементов множества
int QuantitySum (struct TSet *theSet)
{
   int sum= 0;
   while (theSet)
   {
      sum+= theSet->data;
      theSet= theSet->next;
   }
   return sum;
}
//----------------------------------------------//
// Печать всех элементов множества
void QuantityPrint (struct TSet *theSet)
{
   while (theSet)
   {
      printf("%d ", theSet->data);
      theSet= theSet->next;
   }
   printf("\n");
}
//----------------------------------------------//
// Генерация случайным образом эелементов всех подмножеств
void Generate (struct TSet **theSet, int theLength)
{
   srand(time(0));
   int i;
   for (i= 0; i < theLength; ++i)
      theSet[i]= 0;
   for (i= 0; i < theLength*5; ++i)
      QuantityAdd(&theSet[rand() % theLength], rand() % 10);
}
//----------------------------------------------//
// Песать всех подмножеств данного множества
void Print (struct TSet **theSet, int theLength)
{
   int i;
   for (i= 0; i < theLength; ++i)
      QuantityPrint(theSet[i]);
}
//----------------------------------------------//
// Поиск и вывод всех подмножеств, сумма элементов которого
// равна заданному значению
int Find (struct TSet **theSet, int theLength, int theS)
{
   int isFind= 0;
   int i;
   for (i= 0; i < theLength; ++i)
      if (theS == QuantitySum(theSet[i]))
      {
         QuantityPrint(theSet[i]);
         isFind++;
      }
   return isFind;
}
//----------------------------------------------//

int main (int argc, char **argv)
{
   int n;
   printf("n=");
   scanf("%d", &n);
   struct TSet **set= malloc(sizeof(struct TSet) * n);
   Generate(set, n);
   Print(set, n);

   int s;
   printf("s=");
   scanf("%d", &s);
   if (!Find(set, n, s))
      printf("not found\n");

   // Очистка памяти для очистки совести :-)
   int i;
   for (i= 0; i < n; ++i)
      QuantityDel(&set[i]);
   free(set);

   return 0;
}

Подмножества реализованы с помощью односвязного списка. А само множество подмножеств представляет собой простой массив.

--------------------

Я знаю, что ничего не знаю© Сократ
user posted image

kamre

Дата 2.11.2009, 18:39 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

Цитата(t_gran @ 2.11.2009, 07:50)

Ну-у-у..., как то так!:

Что-то я не очень понял это решение. Оно вообще работает?

Вот мой вариант:

Код


#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void print_solution(int N, int *present)
{
    int sum = 0;
    int first = 1;
    int i;
    for (i = 0; i < N; ++i) {
        if (!present[i])
            continue;
        if (first)
            first = 0;
        else
            printf(" + ");
        printf("%d", i + 1);
        sum += i + 1;
    }
    printf(" = %d\n", sum);
}

void enumerate_subsets_internal(int S, int N, int *present, int idx)
{
    if (idx >= N || S < idx + 1)
        return;
    if (S == idx + 1) {
        present[idx] = 1;
        print_solution(N, present);
        present[idx] = 0;
    } else {
        present[idx] = 1;
        enumerate_subsets_internal(S - idx - 1, N, present, idx + 1);
        present[idx] = 0;
        enumerate_subsets_internal(S, N, present, idx + 1);
    }
}

void enumerate_subsets(int S, int N)
{
    int *present = (int*) malloc(sizeof(int) * N);
    memset(present, 0, sizeof(int) * N);
    enumerate_subsets_internal(S, N, present, 0);
    free(present);
}

int main()
{
    int N = 10;
    int S = 13;
    enumerate_subsets(S, N);
    return 0;
}

Результат работы:

Цитата

1 + 2 + 3 + 7 = 13
1 + 2 + 4 + 6 = 13
1 + 2 + 10 = 13
1 + 3 + 4 + 5 = 13
1 + 3 + 9 = 13
1 + 4 + 8 = 13
1 + 5 + 7 = 13
2 + 3 + 8 = 13
2 + 4 + 7 = 13
2 + 5 + 6 = 13
3 + 4 + 6 = 13
3 + 10 = 13
4 + 9 = 13
5 + 8 = 13
6 + 7 = 13

t_gran

Дата 3.11.2009, 04:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Цитата

Что-то я не очень понял это решение. Оно вообще работает?

Обижаете, я никогда непроверенный код не выкладываю. smile

Я не правильно понял постановку задачи. Извиняюсь за дизинформацию. Я-то думал необходимо сгенерировать N-ое количество подмножеств и среди них найти те, сумма которых равна S. Вот что я имел в виду:

user posted image

P.S.: Прошу ещё раз прощения. kamre, +1

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »