Метод определения большего из произведений чисел.

@Sich_Taras · Регистрация: 08.10.2009

Студворк — интернет-сервис помощи студентам

Привет!
Даны два массива. Размер массивов меньше или равен 10000.
В обох массивах записаны числа от 1 до 10.
Нужно определить какое произведение больше: произведение чисел первого массива или второго.
Напишите, пожалуйста, способ или принцип как это сделать на русском. Заранее благодарен.
--------------------------------------------------------------------------------------------------
P.S. Максимальное прозведение можеть быть 10 в 10000-ой степени. Делить после каждого умножение не получится, так как теряется точность.

@kirill29 · 23.10.2009, 23:47

1 Создаем два массива и заполняем их случайными числами от 1 до 10
2 перемножаем элементы каждого массива с помощью, например, цикла for
3 сравниваем полученные значения и выводим ответ, в каком массиве произведение чисел больше.

@Sich_Taras · 23.10.2009, 23:52 **[ТС]**

мне нужно сделать это без использования длинной арифметики.

@GAV_13 · 23.10.2009, 23:53

Сообщение от Sich_Taras

P.S. Максимальное прозведение можеть быть 10 в 10000-ой степени.

зато Максимальная сумма может быть всего лишь 100000, а это уже не так и много

а раз сумма одного ряда, больше суммы другого ряда, то если перемножить элементы рядов, то и произведения будут относится также) для простоты: пусть даны почти равные ряды:

Code
1
2
1 1 1 1 1 1 1 1 1 1  сумма = 10, произведение = 1
1 1 1 1 1 1 1 1 1 2  сумма = 11, произведение = 2

то уже видно, что если 11>10 то 2 должно быть > 1. ЧТД

@Sich_Taras · 24.10.2009, 00:01 **[ТС]**

Сообщение от GAV_13

а раз сумма одного ряда, больше суммы другого ряда, то если перемножить элементы рядов, то и произведения будут относится также) для простоты: пусть даны почти равные ряды:

я не могу найти строгого доказательства, буду тестировать.

@Sich_Taras · 24.10.2009, 00:46 **[ТС]**

Сообщение от GAV_13: зато Максимальная сумма может быть всего лишь 100000, а это уже не так и много а раз сумма одного ряда, больше суммы другого ряда, то если перемножить элементы рядов, то и произведения будут относится также)

Вот пример который опровергает эту теорию:
1 5 1 - сумма 7; произведение 5
3 1 3 - сумма 7; произведение 9

@агерон · 24.10.2009, 01:45

отсортировать 2 массива (алгоритмом QuickSort) и воспринимать их как 2 числа где элемент массива соотвествующая степень числа, а значение элемента множитель степени какое число больше там и произведение больше

@Chea · 24.10.2009, 08:12

Используй сокращения.
сортируем массивы и например в 1 мас. пятерок 587, а во втором 466
во втором все заменяем на 1
в первом на 1 заменяем 466 и оставляем 121

также со всеми остальным числами только еще используем разложение на множители.
должны остаться только 2,3,5,7

@Sich_Taras · 24.10.2009, 13:54 **[ТС]**

Сообщение от агерон

отсортировать 2 массива (алгоритмом QuickSort) и воспринимать их как 2 числа где элемент массива соотвествующая степень числа, а значение элемента множитель степени какое число больше там и произведение больше

Я догадываюсь про что ты написал, но толком не понял. Наведи пожалуйста пример.

Добавлено через 3 минуты

Сообщение от Chea

Используй сокращения.
сортируем массивы и например в 1 мас. пятерок 587, а во втором 466
во втором все заменяем на 1
в первом на 1 заменяем 466 и оставляем 121

также со всеми остальным числами только еще используем разложение на множители.
должны остаться только 2,3,5,7

Можно так сделать только как мне потом сравнивать числа, по их разложениям ?

@odip · 24.10.2009, 22:23

сортируем массивы и например в 1 мас. пятерок 587, а во втором 466

Ничего не нужно сортировать.
В обоих массивах записаны числа от 1 до 10.
Разложим все числа на простые множители.
1=1, 2=2, 3=3, 4=2^2, 5=5, 6=2*3, 7=7, 8=2^3, 9=3^2, 10=2*5.
То есть каждое число в массиве представимо в виде 2^P0 * 3^P1 * 5^P2 * 7^P3,
где P0,P1,P2,P3 - некоторые числа >= 0.
Произведение всех чисел массива представимо в таком же виде - считается просто.

Пусть произведение первого массива в виде: 2^P0 * 3^P1 * 5^P2 * 7^P3
А второго: 2^Q0 * 3^Q1 * 5^Q2 * 7^Q3

Далее - сокращаем оба произведения.
Например P0=10, Q0=25
Значит делим оба числа на 2^10.
Получаем что P0=0, Q0=15.

Добавлено через 3 минуты
В итоге из 8-и чисел P0,P1,P2,P3, Q0,Q1,Q2,Q3 будет максимум 4 числа неравных 0, остальные равны 0.
Если все числа равны 0, значит произведения обоих массивов равны.
Осталось понять как сравнить два таких произведения

Добавлено через 43 минуты
Cравнить можно например с помощью длинной арифметики.
Иначе не знаю как.

Добавлено через 1 минуту
В условии не сказано что нельзя использовать длинную арифметику.

@агерон · 25.10.2009, 03:25

ох господи неужели трудно так понять....

есть 2 числа 213 и 124 сортируем цифры чисел в порядке убывания получаем
321 и 421 т. к. 3*2*1<4*2*1 то произведение цифр 1 числа меньше 2 и для того чтобы точно определить какое из произведений больше на просто нужно сравнить значения соотвествующих разрядов преобразованых чисел вот и все

на тебе программу на С++ и не мучайся

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
 
#define n 10
 
int sortFunction( const void *a, const void *b)
{
 return(((char*)b)[0]-((char*)a)[0]);
}
 
char* initLongNumber(char *longNumber,int countSymbols)
{
 memset(longNumber,0,countSymbols+1);
 randomize();
 for (int i=0;i<countSymbols;i++)
  longNumber[i]=random(10)+'0';
 return longNumber;
}
 
void main()
{
 clrscr();
 char *firstNumber=new char[n+1];
 char *secondNumber=new char[n+1];
 initLongNumber(firstNumber,n);
 initLongNumber(secondNumber,n);
 printf("First massiv: %s\nSecond massiv %s\n\n",firstNumber,secondNumber);
 qsort((void*)firstNumber,n,sizeof(firstNumber[0]),sortFunction);
 qsort((void*)secondNumber,n,sizeof(secondNumber[0]),sortFunction);
 printf("Sorted first massiv: %s\n",firstNumber);
 printf("Sorted second massiv %s\n\n",secondNumber);
 int resultCompareNumber=strcmp(firstNumber,secondNumber);
 if (resultCompareNumber>0)
  printf("Proizvedenie chisel pervogo massiva bolshe");
 else if (resultCompareNumber<0)
       printf("Proizvedenie chisel vtorogo massiva bolshe");
      else printf ("Proizvedenie chisel massivov ravno");
 printf("\n\nPress any key for exit...");
 getch();
 delete []firstNumber;
 delete []secondNumber;
}

#define n 10 - количество элементов в твоих массивах можешь поставить свои ненаглядные 10000
если есть вопросы стучи в Icq #217030476

@Chea · 25.10.2009, 06:36

Сообщение от агерон

ох господи неужели трудно так понять....

Странная у вас арифметика.
Какой массив по вашему алгоритму даст большее произведение
223 или 124
еще пример
5533 или 4444

Добавлено через 19 минут

Сообщение от Sich_Taras

Я догадываюсь про что ты написал, но толком не понял. Наведи пожалуйста пример.

Добавлено через 3 минуты

Можно так сделать только как мне потом сравнивать числа, по их разложениям ?

Что бы быть уверенным что математически все точно и не производить перемножение я пока вижу 1 вариант:

После сокращения получаем только множетели 2,3,5,7

приводим все множители к основанию 2
2= 2^1
3= 2^1,5....(надо высчитать и внести как константу)
5= 2^2,2....
7= 2^2,8....

После сложения степеней легко определить какое число будет больше.

Можно и к другому основанию приводить например 2 = 5^0,3....

Есть риск что разница окажется только, например, в 25 знаке после запятой.
Но поскольку различаются степени значительно - в 1 знаке после запятой то совпадение пожно считать как ошибки округления и что произведения равны

Добавлено через 1 минуту
в смысле не совпадение о отклонение в 25 знаке )))

@temni · 25.10.2009, 06:57

А если сравнить нормы матриц?

@Chea · 25.10.2009, 08:04

Мое мнение - норма для вектора в данном задании не подойдет

прим для 2
норма - это диагональ а произведение - площадь
для 3 мерного вектора норма - диагональ а произведение - объем
и т.д.

В данном вопросе я могу ошибаться - поправте при необходимости

@temni · 25.10.2009, 08:23

Сообщение от Chea

норма - это диагональ а произведение - площадь

о_О. Норма - это действительное число, ставящееся в соответствие по некоему правилу некоему мат. объекту.
три аксомы нормы, разумеется, должны выполняться. однако, офтопик.

Сообщение от Chea

Мое мнение - норма для вектора в данном задании не подойдет

никто не говорит про норму вектора.

Для матрицы можно использовать, например максимум по сумме произведений строчных или столбцевых элементов. Думаю, если правильно подобрать норму, задачу можно свести именно к сравнению норм. Однако, идея с разложением чисел на множители и их сортировкой, возможно, более продуктивна.

@Chea · 25.10.2009, 08:45

А я демал что еще что-то помню

@Sich_Taras · 27.10.2009, 01:44 **[ТС]**

Народ проблема остается !
Помогите , как решить задачу без использования длинной арифметики ?

@temni · 27.10.2009, 03:17

Сообщение от odip

Ничего не нужно сортировать.
В обоих массивах записаны числа от 1 до 10.
Разложим все числа на простые множители.
1=1, 2=2, 3=3, 4=2^2, 5=5, 6=2*3, 7=7, 8=2^3, 9=3^2, 10=2*5.
То есть каждое число в массиве представимо в виде 2^P0 * 3^P1 * 5^P2 * 7^P3,
где P0,P1,P2,P3 - некоторые числа >= 0.
Произведение всех чисел массива представимо в таком же виде - считается просто.

Пусть произведение первого массива в виде: 2^P0 * 3^P1 * 5^P2 * 7^P3
А второго: 2^Q0 * 3^Q1 * 5^Q2 * 7^Q3

Далее - сокращаем оба произведения.
Например P0=10, Q0=25
Значит делим оба числа на 2^10.
Получаем что P0=0, Q0=15.

Добавлено через 3 минуты
В итоге из 8-и чисел P0,P1,P2,P3, Q0,Q1,Q2,Q3 будет максимум 4 числа неравных 0, остальные равны 0.
Если все числа равны 0, значит произведения обоих массивов равны.
Осталось понять как сравнить два таких произведения

Добавлено через 43 минуты
Cравнить можно например с помощью длинной арифметики.
Иначе не знаю как.

Добавлено через 1 минуту
В условии не сказано что нельзя использовать длинную арифметику.

Это самая разумная идея из всех перечисленных.

Из первого массива с числами от 1 до 10 создаём другой, который содержит лишь разложение на степени простых чисел. То есть, например, если видим в первом массиве 1, то ничего не делаем, видим 2 - записываем в новый массив 2, видим 4 - записываем в новый массив два элемента 2, видим 9 пишем "3, 3". (Удобно использовать std::vector<int>). Таким же образом создаём второй "новый массив".

Сортируем. Считаем одинаковые элементы. Получаем четыре числа
p0 - степени двойки
p1 - степени тройки
p2 - степени пятерки
p3 - степени семёрки

Далее, получается нужно сравнить два произведения вида:

2^(p01) * 3^(p11) * 5^(p21) * 7^(p31) и 2^(p02) * 3^(p12) * 5^(p22) * 7^(p32)

То есть задача сводится к отысканию знака разности этих произведений.

Среди степеней одинаковых оснований ищем минимальну., выносим её как общий множитель разности. То есть:

2^(min(p01;p02) * (2^( max(p01;p02)-min(p01;p02)) - 1) * ....

Остаётся сократить на множитель 2^(min(p01;p02))*3^(min(p11;p12))*.... так как он заведомо не равен нулю, и определить знак оставшегося произведения (думаю, INT64 для такого произведения хватит). Знак больше - следовательно, первый массив больше второго в смысле произведения всех элементов.

Не могу гарантировать, что идея будет иметь место. Пробуйте. =).

Кстати, я бы всё таки не оставлял идею о нормах. Из вектора делаем матрицу(как можно более квадратную) и работаем уже с ней. Можно, например, придумать матричный оператор, по энергетической норме которого и сравнивать матрицы. С мат. основанием этой идеи сложнее, зато экзамен автоматом Вам в случае успеха поставят 100% =)

@odip · 27.10.2009, 22:41

думаю, INT64 для такого произведения хватит

Не хватит.
Берем 2^10000 один массив и 3^10000 другой массив.
Нужно вычислить число 2^10000-3^10000.
В данном случае результат ясен.
Но вот например 2^330 и 3^200 сразу не скажешь.

@manfeese · 28.10.2009, 00:46

Предлагаю следующий вариант!
Все числа массива заменить следующим образом:

Code
1
2
3
4
5
6
7
8
9
10
1=exp(ln(1));
2=exp(ln(2));
3=exp(ln(3));
4=exp(ln(4));
5=exp(ln(5));
6=exp(ln(6));
7=exp(ln(7));
8=exp(ln(8));
9=exp(ln(9));
10=exp(ln(10));

При перемножении чисел с одинаковыми основаниями складываються лишь их степени!!!
Таким образом, большим произведением будет то число, у которого большая степень, а сравнить степени труда не составит!!!

Например, два массива: 5533 и 4444, как упоминалось ранее будут иметь вид:

Code
1
2
3
exp(ln(5)+ln(5)+ln(3)+ln(3)) и exp(ln(4)+ln(4)+ln(4)+ln(4)); 
exp(5.4161) и exp(5.5462);
5.4161<5.5462

Значит произведение второго массива будет больше произведения первого массива.

Еще один плюс в данном алгоритме! Чем выше основание логарифма, тем меньше степень числа, т.е. по основанию 10 имеем следующее:

Code
1
2
3
10^(log(5)+log(5)+log(3)+log(3)) и 10^(log(4)+log(4)+log(4)+log(4)); 
10^(2.35218) и 10^(2.40824);
2.35218<2.40824

Новые блоги и статьи Все статьи Все блоги /
изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114

	Метод определения большего из произведений чисел. 23.10.2009, 23:41. Показов 3843. Ответов 23 Метки нет (Все метки) Привет! Даны два массива. Размер массивов меньше или равен 10000. В обох массивах записаны числа от 1 до 10. Нужно определить какое произведение больше: произведение чисел первого массива или второго. Напишите, пожалуйста, способ или принцип как это сделать на русском. Заранее благодарен. -------------------------------------------------------------------------------------------------- P.S. Максимальное прозведение можеть быть 10 в 10000-ой степени. Делить после каждого умножение не получится, так как теряется точность. 0

@kirill29 2098 / 1263 / 173 Регистрация: 01.02.2009 Сообщений: 2,842
	23.10.2009, 23:47
	1 Создаем два массива и заполняем их случайными числами от 1 до 10 2 перемножаем элементы каждого массива с помощью, например, цикла for 3 сравниваем полученные значения и выводим ответ, в каком массиве произведение чисел больше. 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	23.10.2009, 23:52 [ТС]
	мне нужно сделать это без использования длинной арифметики. 0

@агерон 447 / 300 / 65 Регистрация: 12.10.2009 Сообщений: 1,162
	24.10.2009, 01:45
	отсортировать 2 массива (алгоритмом QuickSort) и воспринимать их как 2 числа где элемент массива соотвествующая степень числа, а значение элемента множитель степени какое число больше там и произведение больше 0

@Chea 6 / 6 / 0 Регистрация: 29.09.2009 Сообщений: 41
	24.10.2009, 08:12
	Используй сокращения. сортируем массивы и например в 1 мас. пятерок 587, а во втором 466 во втором все заменяем на 1 в первом на 1 заменяем 466 и оставляем 121 также со всеми остальным числами только еще используем разложение на множители. должны остаться только 2,3,5,7 0

@temni 0 / 0 / 0 Регистрация: 25.10.2009 Сообщений: 22
	25.10.2009, 06:57
	А если сравнить нормы матриц? 0

@Chea 6 / 6 / 0 Регистрация: 29.09.2009 Сообщений: 41
	25.10.2009, 08:04
	Мое мнение - норма для вектора в данном задании не подойдет прим для 2 норма - это диагональ а произведение - площадь для 3 мерного вектора норма - диагональ а произведение - объем и т.д. В данном вопросе я могу ошибаться - поправте при необходимости 0

@Chea 6 / 6 / 0 Регистрация: 29.09.2009 Сообщений: 41
	25.10.2009, 08:45
	А я демал что еще что-то помню 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	27.10.2009, 01:44 [ТС]
	Народ проблема остается ! Помогите , как решить задачу без использования длинной арифметики ? 0