Получить все суммы

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Получить все суммы

Сообщение Vladislav_133 01 окт 2009, 22:09

Сегодня на факультативе по олимпиадному программированию решали такую задачу. Дано число N. Нужно получить все возможные наборы чисел суммы, которых равны этому числу. Суммы, отличающиеся перестановкой считаются тождественными. Ну, например, число 3. Имеем
1+1+1
1+2

На занятии задачу так и не решили. Пошел домой, и как это часто бывыет, понял, в чем была наша ошибка. Пришел домой, набросал программу на С.
Вот ее текст.

Код: Выделить всё
#include <stdio.h>

void sum(int,int,int);

//массив для хранения последовательностей
int ar[40];
int k;
void main()
{
   int j,n=7;
   for(j=1; j<n; j++)   
   {   
      k=0;
      sum(n,j,0);
   }
   return;
}

void sum(int n,int a, int s)
{
   int i,m;
   s=s+a;
   ar[k]=a;
   k++; //на следующий элемент массива
   for(i=a; i<n; i++)
   {
      if(s==n)
      {
         //вывести последовательность
         for(m=0; m<k; m++)
         {
            printf("%d ",ar[m]);            
         }
         printf("\n"); //к следующей строке на экране
         break;
      }
      if(s>n)
      {
         break;
      }
      if(s<n)
      {
         sum(n,i,s);
      }
   }
   k--;
}



Есть ли, по вашему мнению, другие решения?
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Получить все суммы

Сообщение vovan 02 окт 2009, 08:24

Код: Выделить всё
#include <stdio.h>

void sum(int, char*);

int main(void)
{
    int n;
    scanf("%d", &n);
    sum(n, "");
}

void sum(int a, char *st)
{
    int i,j;
    char s[1000];
    for(i=1; i<=a/2; i++) {
        printf("%d+%d%s\n", i, a-i, st);
        sprintf(s, "+%d%s", a-i, st);
        sum(i, s);
        sprintf(s, "+%d%s", i, st);
        sum(a-i, s);
    }
}

Правда я не знаю все ли она варианты выводит, и пока не сообразил как удалить дублируемые варианты
Последний раз редактировалось vovan 03 окт 2009, 18:01, всего редактировалось 1 раз.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Получить все суммы

Сообщение xdsl 02 окт 2009, 08:42

Поднял одно из своих решений, из методички по рекурсивным алгоритмам ftp://shgpi.edu.ru/ftp.vc.shgpi/teaching/metod_materials/posobie_recur.pdf, с пояснялками. Там-же у меня есть вариант перебора с повторениями, правда уже без пояснялок. Стр. 20-22.

Код: Выделить всё
{  Дано число натуральное N. Найти все суммы натуральных чисел,
   с помощью которых его можно представить (без повторений).
   Например: число 8 представимо суммами: 3+4, 2+5, 1+6, 1+2+4
}

var A:array[1..1000]of integer;
    Sum:integer;

procedure Print(Num:integer);
{Выводит на экран содержимое массива A в промежутке [1,Num] }
  var i:integer;
begin
  write('Сумма(',Sum,') = ',a[1]);
  for i:=2 to num do  write('+',a[i]);
  writeln;
end;

procedure CSum(NumA,SumA,Num:integer);
{ процедура перебора всех возможных комбинаций без повторений
   NumA - Количество элементов в рабочем массиве
   SumA - Сумма элементов рабочего массива
   Num  - Рассматриваемый элемент
   }
begin
  if sum=sumA then print(numA)
   { Если сумма элементов массива равна искомому числу,
     то происходит вывод на экран найденных элементов
     и завершение рекурсии }
  else
  if (sumA>sum)or(Num=sum) then exit
   { Иначе, если сумма элементов массива больше искомого числа,
     или рассматриваемый элемент достиг искомого
     (но при этом сумма не найдена),
     то происходит завершение рекурсии }
  else begin
   { определили, что подбор суммы еще не закончен }
   CSUM(NumA,SumA,Num+1);
   { Рекурсивно вызываем процедуру перебора без учета текущего
     рассматриваемого элемента }
   A[NumA+1]:=Num;
   { Учитываем текущее число, занося его в массив ... }
   CSUM(NumA+1,SumA+Num,Num+1);
   { ... и снова производим рекурсивный вызов, уже с
     новым количеством элементов массива и их суммой }
  end;
end;

begin
readln(sum);
{ вводим искомое число }
CSUM(0,0,1);
{ вызываем процедуру перебора }
end.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Получить все суммы

Сообщение xdsl 02 окт 2009, 09:18

Да, вот кстати, в удобочитаемом виде решение задачи на сумму без повторений: http://shgpi.edu.ru/docs/src/sum/sum2.html
и с повторениями: http://shgpi.edu.ru/docs/src/sum/sum3.html
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Получить все суммы

Сообщение vovan 02 окт 2009, 09:19

Код: Выделить всё
#include <stdio.h>
#include <string.h>

void sum(int a, int n, char *st);

int main(void)
{
    int i,n;
    scanf("%d", &n);
    for (i=1; i<n; i++)
        sum(i,n,"");
}

void sum(int a, int n, char *st)
{
    int i;
    char s[100];
    printf("%s%d", st, a);
    for (i=0;i<n-a;i++) {
        printf("+1");
    }
    printf("\n");
    sprintf(s, "%d+%s", a, st, strcmp(st, "")?"+":"");
    int fn=(n-a);
    if (fn>a) fn=a;
    for (i=2; i<=fn; i++) sum(i, n-a, s);
}
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Получить все суммы

Сообщение Vladislav_133 02 окт 2009, 14:40

в моем решении, если я не ошибаюсь, просто заменить вызов sum(n,i,s) на sum(n,i+1,s).
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Получить все суммы

Сообщение vovan 02 окт 2009, 16:02

Vladislav_133 писал(а):в моем решении, если я не ошибаюсь, просто заменить вызов sum(n,i,s) на sum(n,i+1,s).

Для того чтобы получить с повторениями? Тогда
Код: Выделить всё
for(i=a; i<n; i++)

заменить на
Код: Выделить всё
for(i=1; i<n; i++)
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Получить все суммы

Сообщение Vladislav_133 02 окт 2009, 20:51

я имел в виду получить только суммы, в которых слагаемые входят один раз.
а то, что ты предлагаешь - все возможные перестановки слагаемых.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Получить все суммы

Сообщение vovan 03 окт 2009, 07:45

Тогда первый код работает верно
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Получить все суммы

Сообщение Vladislav_133 03 окт 2009, 17:37

И так.
Программа 1. Выдает слагаемые, перестановки не учитываются. Слагаемые могут повотряться.

Код: Выделить всё
#include <stdio.h>

void sum(int,int,int);
int ar[40];
int k;
void main()
{
   int j,n=4;
   for(j=1; j<n; j++)   
   {   
      k=0;
      sum(n,j,0);
   }
   return;
}

void sum(int n,int a, int s)
{
   int i,m;
   s=s+a;
   ar[k]=a;
   k++; //на следующий элемент массива
   for(i=a; i<n; i++)
   {
      if(s==n)
      {
         //вывести последовательность
         for(m=0; m<k; m++)
            printf("%d ",ar[m]);            
         printf("\n"); //к следующей строке на экране
         break;
      }
      if(s>n)   break;
      if(s<n)   sum(n,i,s);
   }
   k--;
}


Программа 2. Слагаемые не могут повторяться.

Код: Выделить всё
#include <stdio.h>

void sum(int,int,int);
int ar[40];
int k;
void main()
{
   int j,n=4;
   for(j=1; j<n; j++)   
   {   
      k=0;
      sum(n,j,0);
   }
   return;
}

void sum(int n,int a, int s)
{
   int i,m;
   s=s+a;
   ar[k]=a;
   k++; //на следующий элемент массива
   for(i=a; i<n; i++)
   {
      if(s==n)
      {
         //вывести последовательность
         for(m=0; m<k; m++)
            printf("%d ",ar[m]);            
         printf("\n"); //к следующей строке на экране
         break;
      }
      if(s>n)   break;
      if(s<n)   sum(n,i+1,s);
   }
   k--;
}

Программа 3. Выдает слагаемые, перестановки учитываются. Слагаемые могут повотряться.
Код: Выделить всё
#include <stdio.h>

void sum(int,int,int);
int ar[40];
int k;
void main()
{
   int j,n=4;
   for(j=1; j<n; j++)   
   {   
      k=0;
      sum(n,j,0);
   }
   return;
}

void sum(int n,int a, int s)
{
   int i,m;
   s=s+a;
   ar[k]=a;
   k++; //на следующий элемент массива
   for(i=1; i<n; i++)
   {
      if(s==n)
      {
         //вывести последовательность
         for(m=0; m<k; m++)
            printf("%d ",ar[m]);            
         printf("\n"); //к следующей строке на экране
         break;
      }
      if(s>n)   break;
      if(s<n)   sum(n,i,s);
   }
   k--;
}
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Получить все суммы

Сообщение vovan 03 окт 2009, 18:17

Ясно. Я неправильно понял про неповторяющиеся слагаемые.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron