2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:43 
lim0n в сообщении #370512 писал(а):
Имелось ввиду, что при $n=10$, если в группе не будет числа $2$, то и число $5$ нельзя будет включить, т.к. нельзя найти связанное с ним число. В противном случае, действительно можно, например, определить такую группу $(2,3,5,6,10)$.
Ну так и рассмотрите группу с $2$. Что в неё можно включить?

 
 
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:47 
Все числа кроме $7$.

 
 
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:48 
lim0n в сообщении #370519 писал(а):
Все числа кроме $7$.
Ну а теперь сформулируйте это для произвольного $n$.

 
 
 
 Re: "Числовые группы" C++
Сообщение06.11.2010, 13:34 
venco в сообщении #370521 писал(а):
Ну а теперь сформулируйте это для произвольного $n$.
Если Вы о группе максимального размера, то об этом я уже писал выше - в неё входят все числа от $2$ до $n$ кроме простых $p>\lfloor n/2\rfloor$.

Но я то немного о другом... Если понимать условие задачи дословно
    badgo в сообщении #369225 писал(а):
    Напишите программу,которая по введенному натуральному числу $n$, $2\le n\le 10^9$, выдавала бы количество групп, на которые распадается отрезок натурального ряда от $2$ до $n$.
решение кажется слишком простым: для $n=2$ ни одной, т.к. группа должна быть "совокупностью натуральных чисел"; для $n=3$ тоже ни одной, т.к. числа $2$ и $3$ несвязанные; для $n>3$ единственная группа. И где тут программирование?
Я же рассуждал о максимальном количестве групп, которые можно построить из натурального ряда от $2$ до $n$.
Кстати, как вариант усложнения задачи - найти максимальное количество групп, на которые распадается отрезок натурального ряда от $2$ до $n$.

 
 
 
 Re: "Числовые группы" C++
Сообщение06.11.2010, 15:27 
Согласен, что условия недостаточно корректны. Я их понял так, что, во-первых, группа может содержать одно число, и во-вторых, любая пара "связанных" чисел принадлежит одной группе. С этими уточнениями решение отнозначно.

 
 
 
 Re: "Числовые группы" C++
Сообщение15.11.2010, 13:07 
Аватара пользователя
А мне вдруг показалось все очень простым.
Наверное, ищется все-таки минимальное количество групп, т.к. максимальное = n-1 (каждое число образует группу).
Все числа до n/2 и все составные <= n образуют одну большую группу. (от любого до любого можно добраться через умножение и деление на простое, не вылезая за n)
А вот простые >n/2 остаются в одиночестве, т.е. каждое из них образует одноэлементную группу.
Остается только подсчитать кол-во простых от n/2 до n
и прибавить 1.
Или я в чем-то ошибаюсь ?

 
 
 
 Re: "Числовые группы" C++
Сообщение16.11.2010, 10:51 
Day в сообщении #375368 писал(а):
А мне вдруг показалось все очень простым.
Наверное, ищется все-таки минимальное количество групп, т.к. максимальное = n-1 (каждое число образует группу).
Даже ещё проще.
Например, из условия
    badgo в сообщении #369225 писал(а):
    Назовем совокупность натуральных чисел "группой", если для каждой пары чисел можно ...
можно предположить, что в группе не может быть менее пары чисел.

 
 
 
 Re: "Числовые группы" C++
Сообщение16.11.2010, 15:06 
Аватара пользователя
linOn, Если пар чисел нет (множество пар - пусто) то об этих несуществующих парах можно говорить все, что угодно, и все будет правда!
Взгляньте сюда
topic36983.html

 
 
 [ Сообщений: 23 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group