powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите оптимизировать индусокод
15 сообщений из 15, страница 1 из 1
Помогите оптимизировать индусокод
    #38891796
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дано число N.Нужно найти 2 числа A и B сумма который равна числу N=A+B и наибольший общий делитель этих чисел максимален.Нужна помощь в оптимизации,программа очень долго работает на больших числах на подобии 10^9.
Код: plaintext
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.
#include <iostream>
#include <stdio.h>


using namespace std;

int nod(int a, int b)
{
	while ((a != 0) && (b != 0))
	{
		if (a > b)
			a = a-b;
		else b = b - a;
	}
	return (a);
}
int main()
{
	
	int n,a,b;
	cin >> n;
	int maxNod = 0;
	int maxA, maxB;
	b = n;
		for (int a = 1; a <= n/2; ++a)
		{
			
			b = n - a;
			if (nod(a, b) >= maxNod)
			{
				maxA = a;
				maxB = b;
				maxNod = nod(a, b);
			}

		}cout << maxA << " " << maxB;
		
	return 0;
}
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891810
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
const int primaries[] = {2,3,5,7,11,13,...}; // google "prime numbers table"

main()
{
	int n;
	cin >> n;
	if (n <= 1)
	{
		cout << "WTF?"
		return 1;
	}
	for (int i = 1; i <= sizeof(primaries)/sizeof(it); ++i)
	{
		if (n % primaries[i] == 0)
		{
			int a = n/primaries[i];
			cout << a << " " << n-a;
			break;
		}
	}
	return 0;
}


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891813
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,спасибо.
1.Сюда запихнуть простые числа?
Код: plaintext
1.
const int primaries[] = {2,3,5,7,11,13,...};


2.Что такое it?
Код: plaintext
1.
for (int i = 1; i <= sizeof(primaries)/sizeof(it); ++i)
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891815
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаванЧто такое it?
int :)
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891817
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но думаю что для чисел порядка 10^9, int опасно использовать.
Лучше int64_t.
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891818
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Преобразовал,на первом же тесте не верно.при вводе 10ти должно выдать две 5ки выдает 2 и 8.
Код: plaintext
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.
#include <iostream>
#include <stdio.h>

using namespace std;



int main()
{
	const int primaries[] = { 2, 3, 5, 7, 11, 13,...};
	int n;
	cin >> n;
	if (n <= 1)
	{
		cout << "WTF?"
			return 1;
	}
	for (int i = 1; i <= sizeof(primaries) / sizeof(int); ++i)
	{
		if (n % primaries[i] == 0)
		{
			int a = n / primaries[i];
			cout << a << " " << n - a;
			break;
		}
	}
	return 0;
}
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891829
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаванПреобразовал,на первом же тесте не верно.при вводе 10ти должно
выдать две 5ки выдает 2 и 8.
А самостоятельно догадаться, что "it" - не единственная опечатка, а массивы нумеруются с
нуля?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891832
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,ой не заметил,сорян
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891836
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Какие то тесты программа умудряется просирать,не могу понять в чем траблы,на компе все пашит
Код: plaintext
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.
#include <iostream>
#include <stdio.h>

using namespace std;



int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	const long long int primaries[] = {2, 3, 5, 7, 11, 13,17,22,23};
	long long int n;
	cin >> n;
	
	for (long long int i = 0; i <= sizeof(primaries) / sizeof(long long int); ++i)
	{
		if (n % primaries[i] == 0)
		{
			long long int a = n / primaries[i];
			cout << n-a << " " << a;
			break;
		}
	}
	
	return 0;
}
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891852
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
С какого перепою у тебя 22 попало в список простых?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891856
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,сам хз,надо пойти и поспать ,а то скоро будет 2+2=5:)Но оно не как не влияет на самом деле.
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891866
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пойди и поспи. Может, потом до тебя дойдут две вещи:
1) В этой таблице должны быть ВСЕ простые числа из заданного диапазона
2) Почти для половины N эта задача имеет больше одного решения. Намного больше.
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891879
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,я знаю что она имеет больше одного решения,надо вывести любое,все туда не запишешь(
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38891908
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ванмомас намбаван,

авторна больших числах на подобии 10^9
таблицу простых чисел то побольше надо делать

достаточно проверять 2,3, 6k-1, 6k+1

и nod оптимальнее можно искать Алгоритм Евклида
...
Рейтинг: 0 / 0
Помогите оптимизировать индусокод
    #38895123
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, подумалось: ноль ведь можно делить на любое число без остатка. Следовательно любое
число - его делитель. В этом случае решение задачи сводится к
Код: sql
1.
2.
a = n;
b = 0;


поскольку a это общий делитель и для самого а, и для нуля, а большего делителя у них быть
уже не может.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
15 сообщений из 15, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите оптимизировать индусокод
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]