Задача в Delphi. Объясните смысл!

[Sianessa]

В общем так: дали решить задачи, а я не могу понять, чего от меня хотят, т.е. не понимаю смысл задачи и не могу составить алгоритм решения. Решение задачи не нужно, напишу сама скорее всего, а вот что делать, зачем и почему, объясните пожалуйста:

1. Дано натуральное число. Составить программу, которая представляет данное число в виде суммы квадратов натуральных чисел, содержащей минимальное число слагаемых.
Например 9=3^2
12=2^2+2^2+2^2
23=3^2+3^2+2^2+1^2

[Sazary]

Ну вот какие мысли:
имхо решать нужно рекурсией.
В функцию (которая будет рекурсивно вызываться) передаете текущую сумму квадратов (ту, что уже накопилась) и строку (вида 3^2+...и т.д).
Если сумма превышает исходное число, то выходим (и возвращаем, например, false).
Если сумма равна исходному числу, то выводим строку и возвращаем true.
Если сумма меньше числа, то
идем в цикле от квадратного корня числа до 1.
Если счетчик в квадрате + накопившаяся сумма не больше исходного числа, то (в самой функции еще нужно объявить строку-буфер) в строку-буфер пишем переданную функции строку "+счетчик^2" и вызываем себя (функцию) с параметрами: текущая сумма (которая в аргументах функции) + счетчик в квадрате, строка-буфер.

В общем, как-то так. Надеюсь, что-нибудь понятно.
Решал подобные задачи.. Особо сложного там ничего нет.

[Sianessa]

Sazary, э-э... Я что-то вообще запуталась Т_Т Не могли бы как-нить на примере хотя бы объяснить, т.е. что-то типа алгоритма сделать?
И что значит - "рекурсией"?
Первый раз с такой задачкой столкнулась и в полном тупике сижу...

[Sazary]

Sianessa, если вы не знакомы с рекурсией, то вам обязательно нужно с ней познакомиться.
Попробую на примере.

Есть число N. Пусть это будет 10.
Сразу определяем условие, при котором нужно закончить все действия - нашли нужные слагаемые.

Итак. Идем в цикле от trunc(sqrt(N)) до 1. (надеюсь, понятно, почему нужно идти от большего к меньшему и почему именно от квадратного корня числа?)

Квадратный корень из 10 (округленный) = 3.
3^2 = 9. Число меньше исходного. Берем его как первое слагаемое.
Снова идем в цикле от trunc(sqrt(N)) до 1.
3^2 + 3^2 = 18 > 10.
3^2 + 2^2 = 13 > 10.
3^2 + 1^2 = 10 - то, что нужно!

Как-то так.

[Sianessa]

Sazary, с рекурсией не знакома никак.
Последую вашему совету непременно, ибо она мне тут нужна судя по всему.
Про корень квадратный всё понятно.
Картина уже яснее стала кажись
Вы говорили что решали подобные задачи, а у вас случайно чего-то похожего не завалялось?
Если да, то не могли бы поделиться?
Мне важна даже больше сама наглядность и сам алгоритм, ибо у меня даже с алгоритмами больше проблем чем с решением, т.к. препод без алгоритмов задачи не принимает.

[Sazary]

Вы говорили что решали подобные задачи, а у вас случайно чего-то похожего не завалялось?

Да я ее, собственно, уже написал )

uses crt;
var
N : integer;

function fun(N : integer; tekS : integer; tekSTR : string) : boolean;
var
S,i : integer;
bstr : string;
begin
 { если сумма больше числа, то слагаемые подобраны неверно }
if tekS>N then
 begin
 fun := false;
 exit;
 end
 { если сумма равна числу, то выводим его }
else if tekS = N then
 begin
 writeln(tekSTR);
 fun := true;
 exit;
 end;
{---}

for i:= trunc(sqrt(N)) downto 1 do
 begin
 S :=tekS+sqr(i);
 if S<=N then  { если текущее значение счетчика в квадрате
  плюс текущая сумма не превышает число, то ... }
  begin
  if tekSTR='' then  { если строка пустая (еще нет первого слагаемого) }
    begin
    Str(i,bstr);
    bstr := bstr + '^2 ';  { кладем туда i^2 }
    end
  else             { иначе добавляем "+i^2 " }
   begin
   Str(i,bstr);
   bstr := tekSTR + '+ ' + bstr +'^2 ';
   end;

   if fun(N,S,bstr) then
     begin
     fun := true;
     exit;
     end;

  end; {for}

 end;


end;
{--------}

begin
clrscr;
readln(N);

fun(N,0,'');

readln;
end.

[Sianessa]

Sazary, хм, быстро вы, однако
Спасибо

Только эмм, не понятно, что есть crt и clrscr ?
Оно ругаецо у меня почему-то =__=

[Sazary]

что есть crt и clrscr ?

CRT - модуль для управления вводом-выводом.
В данной программе из него используется только процедура очистки экрана clrscr;

быстро вы, однако

Говорю ж, что ничего сложного )

[Sianessa]

Sazary, а где его взять, модуль этот?
Он пишет что файл crt.dcu не найден =___= и не хочет программу запускать Т_Т
И по-моему это с паскаля, может его нет в делфи?

[Sazary]

Sianessa, в принципе, вы просто можете удалить строки

uses crt;

и

clrscr;

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

upd Сейчас проверил - у меня тоже не находит ) ну значит просто удалите строчки.