2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 "Числовые группы" C++
Сообщение02.11.2010, 14:34 


02/11/10
43
"Числовые группы".
Два натуральных числа, больших 1, назовем "связанными", если одно получается из другого умножением на какое-то простое число. Например, числа 2 и 10 связаны,а 21 и 85 нет. Назовем совокупность натуральных чисел "группой", если для каждой пары чисел можно подобрать цепочку чисел, их связывающую, такую, что каждые два соседних числа в этой цепочке связаны. Например, совокупность (3,6,30,51) - группа, а (3,4,6,30) нет. Напишите программу,которая по введенному натуральному числу n(2<=n<=10^9) выдавала бы количество групп, на которые распадается отрезок натурального ряда от 2 до n.

Помогите решить задачу.Несколько раз прочитал условие, ничего толком не понял. Что такое связанные числа разобрался, а про группу ничего не понял.

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение02.11.2010, 14:58 
Заслуженный участник
Аватара пользователя


07/01/10
2015
badgo в сообщении #369225 писал(а):
а про группу ничего не понял.

Возьмём любые два числа из {3,6,30,51}, напр. 6 и 51. Цепочка будет такая: (6,3,51) (соседние элементы связаны: $6=3\cdot 2$, $51=3\cdot 17$).

-- Вт ноя 02, 2010 15:11:00 --

Наверное я тоже что-то не понял, ибо второе множество тоже группа.
3 и 4: (3,6,2,4)
3 и 6: (3,6)
3 и 30: (3,6,30)
4 и 6: (4,2,6)
4 и 30: (4,2,6,30)
6 и 30: (6,30)
Может автор задачи подразумевал, что в цепочке разрешается использовать только числа из исходного множества? (Не люблю такие задачи, где авторы даже не потрудились ей качественно сформулировать.)

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение02.11.2010, 16:06 


02/11/10
43
Вообщем бред какой-то)
Завтра еще уточню правильность условия.

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 07:44 


16/06/10
199
badgo в сообщении #369254 писал(а):
Вообщем бред какой-то
Всё сформулировано достаточно полно. Цепочки для группы ${3,6,30,51}$:
$3,6:\ (3,6)$
$3,30:\ (3,6,30)$
$3,51:\ (3,51)$
$6,30:\ (6,30)$
$6,51:\ (6,3,51)$
$30,51:\ (30,6,3,51)$

caxap в сообщении #369232 писал(а):
Наверное я тоже что-то не понял, ибо второе множество тоже группа.
При анализе Вы откуда-то берёте число $2$, а его во второй группе нет.
И вообще, видно, что все числа в группе должны иметь общий делитель, а во второй группе это условие не выполняется для пары чисел $3,4$.

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 12:28 
Заслуженный участник
Аватара пользователя


07/01/10
2015
lim0n в сообщении #369433 писал(а):
При анализе Вы откуда-то берёте число $2$, а его во второй группе нет.

Да, но ведь в задании не сказано, что можно брать числа только из рассматриваемого множества. Ну допустим, это подразумевалось.
lim0n в сообщении #369433 писал(а):
И вообще, видно, что все числа в группе должны иметь общий делитель

Множество {2,3,6} не имеет общего делителя (кроме 1), тем не менее
2,3: (2,6,3)
3,6: (3,6)
2,6: (2,6)

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 15:39 


16/06/10
199
badgo в сообщении #369225 писал(а):
Назовем совокупность натуральных чисел "группой", если для каждой пары чисел можно ...
Скорее всего имелось ввиду - "для каждой пары чисел группы можно ..."


lim0n в сообщении #369433 писал(а):
что все числа в группе должны иметь общий делитель
Да, с этим утверждением я погорячился.

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 15:48 
Заслуженный участник


04/05/09
4596
В общем, badgo, условия вроде уточнили. ;-)
А дальше надо подумать, какими должны быть два числа, чтобы между ними нельзя было проложить путь среди чисел <=n?

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 19:30 


02/11/10
43
В общем ладно...Все равно ничего не понял...Забью на эту задачу пожалуй =)

(Оффтоп)

В общем или вообщем? :-)

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 19:42 
Заслуженный участник


04/05/09
4596

(Оффтоп)

badgo в сообщении #369621 писал(а):
В общем или вообщем? :-)
http://www.gramota.ru/slovari/dic/?word=%E2%EE%EE%E1%F9%E5%EC&all=x

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение03.11.2010, 20:04 


02/11/10
43

(Оффтоп)

Угу,уже тоже погуглил)

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:08 


16/06/10
199
badgo в сообщении #369621 писал(а):
Забью на эту задачу пожалуй =)
:cry:

Ну, а если серьёзно...
venco в сообщении #369528 писал(а):
какими должны быть два числа, чтобы между ними нельзя было проложить путь среди чисел <=n?
Если $p$ и $q$ - простые и $pq>n$, для них нельзя подобрать связывающую их цепочку. Как частный случай, при заданном $n$ в группе не может быть простых чисел $>\lfloor n/2\rfloor$. Но не вижу, что это может дать кроме максимального размера группы при заданном $n$.
А поиск групп? Построить группу максимального размера и после удалять из неё числа?.. Или наоборот, пойти снизу вверх (for i=2 to n)?.. Кстати, это мне больше нравится. Или искать пути в графе?.. Но уж больно условие "негуманное" ($2\le n\le 10^9$), таблица смежности получится немалая. :-(

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:18 
Заслуженный участник


04/05/09
4596
lim0n в сообщении #370482 писал(а):
Если $p$ и $q$ - простые и $pq>n$, для них нельзя подобрать связывающую их цепочку.
Неправильно. $3$ и $5$ находятся в одной группе при $n=10$.

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:26 


16/06/10
199
venco в сообщении #370492 писал(а):
Неправильно.
Тут как раз - "Как частный случай ..." :-) $2\cdot 5=10$

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:28 
Заслуженный участник


04/05/09
4596
lim0n в сообщении #370499 писал(а):
venco в сообщении #370492 писал(а):
Неправильно.
Тут как раз - "Как частный случай ..." :-) $2\cdot 5=10$
Почему же "частный", если случай самый что ни на есть общий?

 Профиль  
                  
 
 Re: "Числовые группы" C++
Сообщение05.11.2010, 16:42 


16/06/10
199
Имелось ввиду, что при $n=10$, если в группе не будет числа $2$, то и число $5$ нельзя будет включить, т.к. нельзя найти связанное с ним число. В противном случае, действительно можно, например, определить такую группу $(2,3,5,6,10)$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: AntonioVivaldi


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group