Автор: vovsik 2.06.2004 22:37
Не пойму. Вот задачка.
Дан неубывающий массив положительных чисел. найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза) .
Автор: GLuk 2.06.2004 22:57
А что конкретно не поймешь?
Как ее на паскале написать? Или мож на асме?
Автор: virt 2.06.2004 23:38
Код
{$A+,B-,D-,E+,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 16384,0,655360}
program minnemogu;
const Max_Chislo=1000;
var i,j,n:word;
a:array[1..64000]of byte;
x:word;
l:longint;
Max_Summa:word;
begin
fillchar(a,sizeof(a),0);
read(n);
Max_Summa:=0;
for i:=1 to n do
begin
read(x);
Max_Summa:=Max_Summa+x;
a[x]:=a[x]+1;
end;
for i:=0 to Max_Summa-1 do
begin
if a[i]>1 then
begin
l:=longint(i)+j;
if l<=Max_Summa then a[l]:=a[l]+1;
end;
for j:=i+1 to Max_Summa do
if (a[i]>0) and (a[j]>0) then
begin
l:=longint(i)+j;
if l<=Max_Summa then a[l]:=a[l]+1;
end;
{ writeln(i);}
end;
for i:=1 to Max_Summa+1 do
if a[i]=0 then break;
writeln(i);
readln;
end.
Вот вроде должно работать.
Автор: vovsik 3.06.2004 0:01
а Если я добавлю, что число действий - порядка размера массива? Что с этой шнягой делать?запарился совсем!
Автор: zx1024 3.06.2004 19:42
Код
S=1;
for i := 1 to n do
begin
if a[i] > S then
break
S := S + a[i]
end;
r := S
a - исходный НЕУБЫВАЮЩИЙ массив, n - его размер,
в r будет результат.
Автор: GLuk 3.06.2004 23:30
оффтоп
Что-то тебя zx1024 давно видно не было??