Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.01.2012, 21:20   #1
Katya20
 
Регистрация: 22.12.2011
Сообщений: 3
По умолчанию ЦИКЛЫ (паскаль) - представить N в виде суммы факториалов натуральных чисел, содержащей наименьшее число слагаемых

помогите с задачей-
задача: дано натуральное число N<=2000000000. представить N в виде суммы факториалов натуральных чисел, содержащей наименьшее число слагаемых
Katya20 вне форума Ответить с цитированием
Старый 08.01.2012, 22:37   #2
whatever
a.k.a. Skull
Форумчанин
 
Регистрация: 17.11.2009
Сообщений: 963
По умолчанию

Код:
program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  slagaemoe=record
    chislo:integer;
    fact:real;
    FactPrev:real;
  end;
  slagaemie=array of slagaemoe;

procedure fact(var a:slagaemoe);
var
  tmp:real;
begin
  a.FactPrev:=a.fact;
  inc(a.chislo);
  a.fact:=a.chislo*a.fact;
end;
procedure WORK(N:real; var M:slagaemie);
var
//  N:real;
//  M:slagaemie;
  tmp,tmp2:real;
  i,k:integer;
  S:string;
begin
//  readln(n);
//  n:=8;
  setlength(m,1);
  m[0].chislo:=1;
  m[0].fact:=1;
  repeat
    fact(m[0]);
  until m[0].fact>=n;
  if m[0].fact=n then
    begin
      writeln(m[0].chislo);
      readln;
      halt;
    end;

//  tmp:=0;
  tmp2:=0;
  k:=0;
  repeat
      tmp:=0;
      for i:=0 to high(m) do
        tmp:=tmp+m[i].FactPrev;
      inc(k);
      setlength(m,length(m)+1);
      m[k].chislo:=1;
      m[k].fact:=1;
      if tmp+m[k].fact=n then
        begin
          for i:=0 to high(m) do
            if m[i].chislo=1 then
              S:=s+IntToStr(m[i].chislo)+'!+'
            else
              S:=s+IntToStr(m[i].chislo-1)+'!+';
          delete(S,length(S),1);
          S:=S+'='+FloatToStr(n);
          writeln(s);
          readln;
          halt;
        end;
      if n<>5 then
        if tmp+2<>n then
          tmp2:=tmp+1
        else
          tmp2:=tmp;
      repeat
        fact(m[k]);
        tmp2:=tmp2+m[k].fact;
      until tmp2>=n;

      if tmp2=n then
        begin
          for i:=0 to high(m) do
            if i=high(m) then
              S:=s+IntToStr(m[i].chislo)+'!+'
            else
              S:=s+IntToStr(m[i].chislo-1)+'!+';
          delete(S,length(S),1);
          S:=S+'='+FloatToStr(n);
          writeln(s);
          readln;
          halt;
        end
      else
      tmp:=tmp2-m[k].Fact;
  until tmp=n ;

    s:='';
    for i:=0 to high(m)-1 do
      S:=s+IntToStr(m[i].chislo-1)+'!+';
    delete(S,length(S),1);
    S:=S+'='+FloatToStr(n);
    writeln(s);
    readln
end;

var
  N:real;
  M:slagaemie;
begin
  readln(n);
//  n:=8;
  WORK(N,M);
end.
Протестировал на паре задач, вроде бы правильно. На счет наименьшего числа слагаемых хз, но тоже вроде бы верно.
Не, нифига, надо что-то другое думать, малёха косячит, всмысле на минимальное количество слагаемых.

Update: не, вообще не смотри сюда, косяков сильно много.
Все тривиальное просто

Последний раз редактировалось whatever; 08.01.2012 в 22:56.
whatever вне форума Ответить с цитированием
Старый 08.01.2012, 22:40   #3
Hacker19_90
Delphi Warrior
Старожил
 
Аватар для Hacker19_90
 
Регистрация: 15.08.2008
Сообщений: 2,502
По умолчанию

Цитата:
+FloatToStr
setlength(m,1);
В паскале? Откуда
Mess with the best, die like the rest. (с) Hackers
Лабораторные, курсовые на Delphi\Pascal\C++
ya.flex-freelance@yandex.ru Icq - 636-954-303
Hacker19_90 вне форума Ответить с цитированием
Старый 08.01.2012, 22:56   #4
whatever
a.k.a. Skull
Форумчанин
 
Регистрация: 17.11.2009
Сообщений: 963
По умолчанию

Мда, действительно... Просто меня клинит бывает, кажется, что паскаль и дэлфи синонимы. Действительно, в паскале не получится. Ну массив, например, можно не динамический задать, да и со строками связываться не обязательно, но тут проблема в алгоритме. У меня считает верно, но много лишних слагаемых (200=5!+4!+4!+3!+3!+3!+2!+2!+2!+2!, когда 2!+2!+2!=3!).
Вообще, тут задача больше математическая, чем програмистская.
Все тривиальное просто

Последний раз редактировалось whatever; 08.01.2012 в 22:58.
whatever вне форума Ответить с цитированием
Старый 09.01.2012, 00:36   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

ребят, я может туплю, но разве минимальное число слагаемых не будет, если следовать следующему простому правилу:
находим максмальное число K, такое, что K!<=N, а (K+1)!>N
потом из N вычитаем K! (K! добавляем в найденные слагаемые) и результат записываем в N:
N := N - K!
повторяем, пока N>0.
всё.
реализовать такое - десять минут...

или я проглядел простые и очевидные ошибки в подобном алгоритме?!

примерное решение по моему алгоритму выглядит так:
Код:
var i, MaxK, P, N : LongInt;
  Fact : array[1..14] of LongInt;
begin
  WriteLn('Введите число N: ');
  Readln(N);

  if (N<0) or (N>2000000000) then begin
    WriteLn('Ошибочное N! Выход из программы!'); Halt(100)
  end;

  {заполним таблицу факториалов}
  P := 1;
  MaxK := 0;
  repeat
    inc(MaxK);
    P:=P*MaxK;
    if P<=N then
        Fact[MaxK] := P;
  until P>N;
  Dec(MaxK);

  {выдача результата}
  WriteLn;
  Write(N,' = ');
  i:=MaxK;
  while N>0 do begin
    while (N>0) and (Fact[i]<=N) do begin
      Write( i,'!');
      N := N - Fact[i];
      if N>0 then Write(' + ');
    end;
    Dec(i);
  end;

  Readln;
end.
пример решения:
Цитата:
Код:
200 = 5! + 4! + 4! + 4! + 3! + 2!

Последний раз редактировалось Serge_Bliznykov; 09.01.2012 в 00:57.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 09.01.2012, 00:42   #6
Hacker19_90
Delphi Warrior
Старожил
 
Аватар для Hacker19_90
 
Регистрация: 15.08.2008
Сообщений: 2,502
По умолчанию

Цитата:
но разве минимальное число слагаемых не будет, если следовать следующему простому правилу:
Действительно так!
Mess with the best, die like the rest. (с) Hackers
Лабораторные, курсовые на Delphi\Pascal\C++
ya.flex-freelance@yandex.ru Icq - 636-954-303
Hacker19_90 вне форума Ответить с цитированием
Старый 09.01.2012, 01:19   #7
whatever
a.k.a. Skull
Форумчанин
 
Регистрация: 17.11.2009
Сообщений: 963
По умолчанию

Да, чет я правда в дебри полез...
Все тривиальное просто
whatever вне форума Ответить с цитированием
Старый 09.01.2012, 01:21   #8
Hacker19_90
Delphi Warrior
Старожил
 
Аватар для Hacker19_90
 
Регистрация: 15.08.2008
Сообщений: 2,502
По умолчанию

Код:
program fact;
uses
    crt;
var
    n: LongInt;
    i: LongInt;

function fact (const n: LongInt): LongInt;
var
    i: LongInt;
    s: LongInt;
begin
    if n = 0 then s := 1
    else
    begin
        s := 1;
        for i := 1 to n do
            s := s * i;
    end;
    fact := s;
end;

begin
    clrscr;
    Writeln ('Enter number: ');
    {$I-}
    Readln (n);
    if IOResult <> 0 then
    begin
        Writeln ('Error!!!');
        exit;
    end;
    {$I+}
    Write (n, ' = ');
    while n > 0 do
    begin
        for i := 1 to n do
        begin
            if (fact(i+1) > n) then
            begin
                 Write (i, '! + ');
                 n := n - fact(i);
                 break;
            end;
        end;
    end;
    ReadKey;
end.
как-то так
Изображения
Тип файла: jpg Снимок.JPG (19.2 Кб, 67 просмотров)
Mess with the best, die like the rest. (с) Hackers
Лабораторные, курсовые на Delphi\Pascal\C++
ya.flex-freelance@yandex.ru Icq - 636-954-303

Последний раз редактировалось Hacker19_90; 09.01.2012 в 01:25.
Hacker19_90 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Можно ли число N представить в виде сумы двух квадратов натуральных чисел? Dima170792 Помощь студентам 2 24.06.2011 08:53
число в виде суммы квадратов натуральных чисел gambuz Паскаль, Turbo Pascal, PascalABC.NET 0 04.10.2010 11:07
C++/ Все способы представления заданного натурального числа N в виде суммы двух кубов натуральных чисел / acko Помощь студентам 1 25.09.2010 12:15
Определить представимо ли число содержащиеся в ячейке 0200 в в виде суммы 2х простых чисел. Lenusy Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 0 06.10.2009 08:26
Дано натуральное число n. Можно ли представить его в виде суммы двух квадратов натуральных чисел? Сеня Помощь студентам 3 29.01.2009 01:17