Приизведение чисел

[VictorS]

Дано два наборы чисел, в обох одинаковое количество чисел. Каждое число <= 10, количество чисел до 100000; Нужно узнать какое произведение больше - первого набора или другого? Конечно это надо сделать без длинной арифметики.

Думал об обчиселнии по модулю, но это неверно (( Помогите пожалуйста. Спасибо.

[werser]

var 
a:array [100000] of integer;
b:array [100000] of integer;
i,j,d1,d2,N:integer;
begin
randomize;
N:=1000; d1:=1;d2:=1;
for i:=1 to N do 
begin 
a[i]=random(10);
end;
for i:=1 to N do 
begin b[i]=random(10);
end;

for i:=1 to N do 
begin
d1:=d1*a[i];
end;

for i:=1 to N do 
begin
d2:=d2*b[i];
end;

if d1>d2 then Write("V pervou bolwe");
 if d2>d1 then Write("V vtorou bolwe")
else Write("Ravno");

[VictorS]

10^100000 далеко выходит за integer...

[Plague]

а если пропробовать сортировку подсчетом.

var a,b:array [1..10] of longint;
    x,y,i,n:longint;
begin
  readln(n);
  for i:=1 to N do 
    begin 
      x:=random(9)+1;
      y:=random(9)+1;
      inc(a[x]);
      inc(b[y]);
    end;

[Plague]

И почитав Основную теорему арифметики

можно сделать так:

var a,b:array [2..7] of integer;
    x,y,i,n:integer;
begin
  readln(n);
  randomize;
  for i:=1 to N do 
    begin 
      x:=random(9)+1;
      case x of
        2,3,5,7:inc(a[x]);
        4:inc(a[2],2);
        6:begin inc(a[2]);inc(a[3]);end;
        8:inc(a[2],3);
        9:inc(a[3],2);
       10:begin inc(a[2]);inc(a[5]);end;
      end;
      y:=random(9)+1;
      case y of
        2,3,5,7:inc(b[y]);
        4:inc(b[2],2);
        6:begin inc(b[2]);inc(b[3]);end;
        8:inc(b[2],3);
        9:inc(b[3],2);
       10:begin inc(b[2]);inc(b[5]);end;
      end;
    end;
  
  for i:=2 to 7 do
    case i of
      2,3,5,7: write(i,'^',a[i],' * ');
    end;
  
  writeln;
  
  for i:=2 to 7 do
    case i of
      2,3,5,7: write(i,'^',b[i],' * ');
    end;
end.

вводя 100000
у меня получилось так

2^77196 * 3^44666 * 5^11218 * 7^11028  
2^77978 * 3^44470 * 5^11181 * 7^11039

у и от сюда зная степени надо определить какое число больше.

[VictorS]

у и от сюда зная степени надо определить какое число больше.

А как?
Спасибо.

[Plague]

А как?

А вот надо подумать.
Можно прологорифмировать оба выражения.
в случае:

2^77196 * 3^44666 * 5^11218 * 7^11028  
2^77978 * 3^44470 * 5^11181 * 7^11039

получаем:

77196*ln(2) + 44666*ln(3) + 11218*ln(5) + 11028*ln(7) ≈ 142092,98
77978*ln(2) + 44470*ln(3) + 11181*ln(5) + 11039*ln(7) ≈ 142381,55

ну и какое из них больше?

[Serge_Bliznykov]

Ого... уже логарифмирование пошло..
Господа, а простите за наивный вопрос.
а так разве не проще:

var  D : Extended;
....
begin
 D := 1;
 for i:=1 to 10000 do
   D := D * (a[i]/b[i])
 if abs(D-1)<0.0000001 then WriteLn('НАБОРЫ РАВНЫ')
 else begin
    if D>1 then WriteLn('Набор A больше') 
    else WriteLn('Набор B больше');
  end;

[Plague]

Extended 3.6 x 10^-4951 .. 1.1 x 10^4932.
так?
предпологаем что:
в а все 10, а в b все 1.
при вводе 100000, получаем D=10^100000. Так?
И вы хотите сказать что это влезет в Extended?

[Serge_Bliznykov]

Plague, убедительно. Действительно, не влезет.
вышеприведённый предложенный мной вариант не покатит.

Тогда можно предложить такой вариант, учитывать
НЕ ВСЕ ЧИСЛА.
сейчас нет свободного времени на реализацию/проверку.
Но общий идея такая - заводим две переменные счётчик элементов по массиву A и отдельный счётчик по массиву B. дальше наращиваем их одновременно,
в цикле сравниваем
если произведение Больше некой константы (ну, допустим 10^10), тогда продолжаем цикл наращивания счётчика по второму массиву (т.е. ТОЛЬКО делим)
если произведение Меньше некой константы (например, 10^-10, то увеличиваем только первый счётчик и только умножаем
Если дошли до конца одного из массивов:
Если ДошлиДоКонца_Первого и число МЕНЬШЕ единицы, значит произведение эл-тов Первого массива МЕНЬШЕ второго.
Если ДошлиДоКонца_Второго и число БОЛЬШЕ единицы, значит произведение эл-тов Первого массива БОЛЬШЕ второго.

Как Вам такой алгоритм?


[добавлено]
p.s. хотя, с другой стороны, не буду утверждать, что подобный алгоритм лучше, эффективнее, быстрее, чем продложенный Вами подсчёт количества сомножителей!!


NB. Кстати, его можно немножко соптимизировать (сократить дробь - отнять от большего числа меньше:
тогда

2^77196 * 3^44666 * 5^11218 * 7^11028
2^77978 * 3^44470 * 5^11181 * 7^11039

превратиться в
1 * 3^196 * 5^37 * 1
2^782 * 1 * 1 * 7^11

хотя... можно это и не делать