Нужна помощь по программке

Rolat · 10.11.2012

Нужна помощь по программке

Итак, надо решить задачу: Какое самое маленькое число делится нацело на все числа от 1 до 20?.
Так вот, есть цикл, который делит некое число на числа от 1 до 20. Как только не делиться, сразу начинает считать новое число и тд. Как сделать, чтобы он нужное число то вывел ??

Вот собственно прога
int main()
{
for(int a=20;a<1000000;a=a+20)
{
for(int b=1;b<=20;b++)
{
if(a%b!=0)
break;
}
}

}
P.S.Вариант поочередно проверять делимость на все числа не катит, ибо не в прикол)

burning_LEGION · 11.11.2012

int main()
{
for(int a=20;a<1000000;a=a+20)
{
for(int b=1;b<=20;b++)
{
if(a%b!=0)
break;
cout <<a;
return 0;
}
}
}

Klez · 11.11.2012

Rolat сказав(ла):
P.S.Вариант поочередно проверять делимость на все числа не катит, ибо не в прикол)

так ты именно это и делаешь, в чем прикол?

Achenar · 11.11.2012

Rolat сказав(ла):
Какое самое маленькое число делится нацело на все числа от 1 до 20?.

Создаешь пустое множество A. Перебираешь все числа от 1 до 20. К каждому применяешь функцию, возвращающую множество простых делителей B( x(14) = {2,7}). Смотришь, является ли B подмножеством A ( если A = { 2, 3, 7 ), то B = {2,7} - является). Если чего-то не хватает ( A = {3,5,13}, B = {2,7} ), то объединяешь множества, простые множители могут повторяться. Например, двоек там будет минимум 4, потому что есть число 16.

Искомое число - результат произведения всех чисел из множества A. Примерный ход алгоритма:

N = 2, B = {2} A = {} -> A = {2}
N = 3, B = {3} A = {2} -> A = {2,3}
N = 4, B = {2,2} A = {2,3 } -> A = {2,2,3}
N = 5, B = {5}, A = {2,2,3} -> A = {2,2,3,5}
N = 6, B = {2,3}, A = {2,2,3,5} -> A не меняется

Второй вариант - искать наименьшее общее кратное между текущим F(N-1) и N, где F(N-1) - число, которое делится на все числа от 1 до N-1. По-моему, оно равно частному произведения чисел и наибольшего общего делителя.

P.S. Можно сильно проще. Если не выходить за пределы задачи, достаточно узнать, какой максимальный простой делитель. Это 19. Перебираем 2,3,5,7,11,13,17,19, какая степень этого делителя меньше 20 - столько их будет в множестве A. То есть 4 двойки, 2 тройки, 1 пятерка, 1 семерка и т.д. Логарифм по основанию 2 и 3 числа 20 в помощь, остальные по одному, потому что больше квадратного корня 20.

avbua · 12.11.2012

А я бы считал так:

{
DWORD a= 20, c;
for(DWORD b=1; b<=20; b++)
{
c= a;
while(a%b)
a+= c;
}
cout <<a;
}

На 5-6 порядков быстрее.

Rolat · 12.11.2012

так ты именно это и делаешь, в чем прикол?

Я имел в виду отдельно считать делимость на каждое число... можно конечно, но ИМХО бред, хотя и быстрее будет.
Совету ув.Achenarа я при всем желании последовать не могу, ибо из серии "все понимаю, только сказать не могу", да и о логарифмах я ни сном ни духом.

int main()
{
for(int a=20;a<1000000;a=a+20)
{
for(int b=1;b<=20;b++)
{
if(a%b!=0)
break;
cout <<a;
return 0;
}
}
}

Это вроде вообще бред...

По сути что надо, если цикл закончился(т.е. проверил делимость на все нужные числа), то число подходит, и надо его вывести на экран. Если число на что-то не делиться, то цикл заканчиваеться раньше времени, и ничего на экран не выводиться... задумка была такая, вот только как реализовать зависимость от работы цикла и выводом на экран не могу придумать.

avbua · 12.11.2012

Rolat сказав(ла):
По сути что надо, если цикл закончился(т.е. проверил делимость на все нужные числа), то число подходит, и надо его вывести на экран. Если число на что-то не делиться, то цикл заканчиваеться раньше времени, и ничего на экран не выводиться... задумка была такая, вот только как реализовать зависимость от работы цикла и выводом на экран не могу придумать.

int main()
{
for(int a=20;a<1000000;a=a+20)
{
for(int b=1;b<=20;b++)
{
if(a%b)
break;
}
if( b==21)
{
cout <<a;
break;
}
}
}

Achenar · 12.11.2012

avbua решил задачу, его решение вроде идеально подходит. Три строчки, считает быстро, никаких замутов из теории множеств и логарифмов

lugal · 12.11.2012

Вопрос решаеться обратным путем.
Разбираете все числа от 2 до 2 на элементарные множители, сохраняете их в массиве (я бы для простоты кода использовал сет), а опосля умножаете все элементарные множители и получаете искомое число.

Achenar · 12.11.2012

lugal сказав(ла):
опосля умножаете все элементарные множители и получаете искомое число

Я правильно понял, в этом сете будет только одна 2?

lugal · 12.11.2012

Achenar сказав(ла):
Я правильно понял, в этом сете будет только одна 2?

Да, вы правы, хрень написал, сет не подходит. Код усложняеться.
Нада подумать над элегантным решением... Но суть та же

Jogger · 12.11.2012

Велосипед изобретаете?
https://ru.wikipedia.org/wiki/Наименьшее_общее_кратное

burning_LEGION · 12.11.2012

Rolat сказав(ла):
Это вроде вообще бред...

возможно =) я не читал что он там написал, вопрос стоял как вывести число, я вывод и добавил, а что считается и правильность смотреть никто не просил

Jogger · 12.11.2012

burning_LEGION сказав(ла):
возможно =) я не читал что он там написал, вопрос стоял как вывести число, я вывод и добавил, а что считается и правильность смотреть никто не просил

Но вывод на экран после break - это бред в любом случае

burning_LEGION · 12.11.2012

Jogger сказав(ла):
Но вывод на экран после break - это бред в любом случае

си подобные языки если после ифа нет фигурных скобок считают что в теле ифа одна следующая операция, т.е. равносильно:
if(a%b!=0)
{
break;
}
else
{
cout <<a;
return 0;
}

lugal · 13.11.2012

burning_LEGION сказав(ла):
си подобные языки если после ифа нет фигурных скобок считают что в теле ифа одна следующая операция, т.е. равносильно:
if(a%b!=0)
{
break;
}
else
{
cout <<a;
return 0;
}

В теории

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

На практике конструкция вида:
for (some_exp_for_100_iteration)
if (some_exp)
some_exp;

в Вижуал студии иногда выполняеться лишь раз.

Как то так:

Код:

#include <stdio.h>

int main()
{
	const size_t max_nmb = 20;

	size_t val = 1;
	for (size_t i = 2; i <= max_nmb; ++i)
	{
		if (val % i != 0)
		{
			size_t tmp_val = val;
			size_t tmp_div = 2;
			size_t tmp_nmb = i;
			while ( tmp_nmb != 1)
			{
				if (tmp_nmb % tmp_div == 0)
				{
					if (tmp_val % tmp_div == 0)
					{
						tmp_val /= tmp_div;
					}
					else
					{
						val *= tmp_div;
					}

					tmp_nmb /= tmp_div;
				}
				else
				{
					++tmp_div;
				}
			}
		}
	}

	printf ("%u", val);
	return 0;
}

Полученній ответ 232792560

avbua · 13.11.2012

lugal сказав(ла):

Как то так:

Код:

#include <stdio.h>

int main()
{
	const size_t max_nmb = 20;

	size_t val = 1;
	for (size_t i = 2; i <= max_nmb; ++i)
	{
		if (val % i != 0)
		{
			size_t tmp_val = val;
			size_t tmp_div = 2;
			size_t tmp_nmb = i;
			while ( tmp_nmb != 1)
			{
				if (tmp_nmb % tmp_div == 0)
				{
					if (tmp_val % tmp_div == 0)
					{
						tmp_val /= tmp_div;
					}
					else
					{
						val *= tmp_div;
					}

					tmp_nmb /= tmp_div;
				}
				else
				{
					++tmp_div;
				}
			}
		}
	}

	printf ("%u", val);
	return 0;
}

Полученній ответ 232792560

У меня в пятом посте короче

Jogger · 13.11.2012

burning_LEGION, да, ты прав, действительно так можно. Хотя вывод на экран у тебя всё равно не в том месте)