Форум 3DNews
Вернуться   Форум 3DNews > Программирование > Программирование

Ответ Создать новую тему
Опции темы Опции просмотра
Непрочитано 26.12.2008, 16:30   [включить плавающее окно]   #1
Alex Buriy
Мужской Новенький
Автор темы
 
Регистрация: 26.12.2008
Unhappy Помогите с Задачей по С++!!! Завтра защита а задача не сделана :(

Помогите пожалуйста у меня защита курсовой завтра по С++ а задача не сделана совсем!!! А в С++ я совсем не шарю!!! помогите пожалуйста!!! Заранее Спасибо!!!

Какое максимальное колличество натуральных чисел от 1 до 10 можно выбрать чтобы среди них не было отличающихся в два раза!!!
Alex Buriy вне форума  
Ответить с цитированием
Непрочитано 12.01.2009, 13:17   [включить плавающее окно]   #2
dark_rex
Мужской Бывалый
 
Регистрация: 05.10.2006
Я что-то сомневаюсь в способности защитить курсовой проект при неспособности решать задачи для тетьего класса. Правильный ответ: 1, 3, 4, 5, 7, 9, т.е. 6 чисел.
1) создаем и заполняем одномерный массив (вектор) числами от 1 до 10;
2) в цикле вида for (i=1, i<11, i++) делаем проверку на неравенство 2 результата от деления чисел друг на друга (нужно либо последовательно делить каждое число на каждое, либо попробовать опимизировать количество операций);
3) при неравенстве подкручиваем счетчик;
4) печатаем значение счетчика.
dark_rex вне форума  
Ответить с цитированием
Непрочитано 01.02.2009, 13:34   [включить плавающее окно]   #3
404
Мужской Умудрённый
 
Регистрация: 04.08.2003
Цитата (dark_rex) »
в цикле вида for (i=1, i<11, i++) делаем проверку на неравенство 2 результата от деления чисел
Каких чисел? Вы озвучили только один параметр, i — количество чисел. Но нужно же перебрать все сочетания из i чисел для каждого i. Что уже не есть тривиально. "3-ий класс" тут, конечно, не при чём.

Вообще это олимпиадная задачка по математике, не по программированию (только диапазон дают больше, скажем, от 1 до 100, чтоб сразу отбросить попытки простого перебора всех сочетаний). Ответ — все числа вида С*4^n, где n >= 0, C — нечётное.
404 вне форума  
Конфигурация ПК
Ответить с цитированием
Непрочитано 01.02.2009, 17:10   [включить плавающее окно]   #4
anonymouse
Женский Продвинутый
 
Регистрация: 04.05.2008
лучше сапоги примерь, сходи на турник. Учиться дальше смысла нет, если ты элементарного не можешь сдать.
__________________
анонимный анонимаус.
anonymouse вне форума  
Ответить с цитированием
Непрочитано 04.02.2009, 00:03   [включить плавающее окно]   #5
dark_rex
Мужской Бывалый
 
Регистрация: 05.10.2006
Цитата (404) »
Цитата (dark_rex) »
в цикле вида for (i=1, i<11, i++) делаем проверку на неравенство 2 результата от деления чисел
Каких чисел? Вы озвучили только один параметр, i — количество чисел. Но нужно же перебрать все сочетания из i чисел для каждого i. Что уже не есть тривиально. "3-ий класс" тут, конечно, не при чём.
Хм, а если рекурсией пока количество двукратных чисел не станет равным нулю?

Цитата
Вообще это олимпиадная задачка по математике, не по программированию (только диапазон дают больше, скажем, от 1 до 100, чтоб сразу отбросить попытки простого перебора всех сочетаний). Ответ — все числа вида С*4^n, где n >= 0, C — нечётное.
А можно вывод данной формулы? Интересно, как его получили...
dark_rex вне форума  
Ответить с цитированием
Непрочитано 04.02.2009, 12:29   [включить плавающее окно]   #6
404
Мужской Умудрённый
 
Регистрация: 04.08.2003
Цитата (dark_rex) »
а если рекурсией пока количество двукратных чисел не станет равным нулю?
А более конкретно это как?

Цитата (dark_rex) »
можно вывод данной формулы?
Задача. Какое максимальное колличество натуральных чисел от 1 до N можно выбрать, чтобы среди них не было отличающихся в два раза?

Решение. Рассмотрим все возможные последовательности из чисел от 1 до N, удовлетворяющие условию задачи, т. е. не содержащие чисел, отличающихся ровно в 2 раза.

Пусть некая послед-ть A содержит число C*2^(2*n + 1), где C — какое-то нечётное число, n ≥ 0.

Тогда A не может также содержать C*2^(2*n), но может содержать C*2^(2*n – 1); но тогда A не может содержать C*2^(2*n – 2), но может C*2^(2*n – 3); и т. д… Аналогично в большую сторону: A не может содержать C*2^(2*n + 2), но может содержать C*2^(2*n + 3); и т. д.

Итак: если некая послед-ть A содержит число C*2^(2*n + 1), то она также содержит цепочку чисел:
C*2^(2*q + 1), C*2^(2*(q+1) + 1), …, C*2^(2*p + 1), где 0 ≤ q ≤ n ≤ p;
или иначе её можно записать как:
C*4^q*2, C*4^(q+1)*2, …, C*4^p*2.
Cнизу эта цепочка может быть органичена числом 2, сверху — N.

Тогда расмотрим послед-ть B, которая, вместо этой цепочки, содержит другую:
C*4^q, C*4^(q+1), …, C*4^p, где 0 ≤ q ≤ n ≤ p;
а все остальные числа в B те же самые, что в A. Такая послед-ть B также удовлетворяет условию задачи. Но, кроме того: если число C*4^(p+1) ≤ N, мы тоже можем включить его в посл-ть B, и такая послед-ть тоже будет удовлетворять условию задачи, но содержать на 1 число больше, чем A. Если же C*4^(p+1) > N, то в B будет столько же чисел, сколько в A.

Итого: для любой послед-ти A, удовлетворяющей условию задачи, и содержащий числа вида C*4^n*2, можно указать послед-ть B, также удовлетворяющюю условию задачи, но содержащюю только числа вида C*4^n, причём количество чисел в B будет больше или равным, чем в A.

А значит, послед-ть, удовлетворяющая условию задачи, и содержащая только числа вида C*4^n и будет той, количество чисел в которой максимально.

Ну и посчитаем количество Q чисел вида C*4^n от 1 до N:
Q = [N/2] + [N/8] + [N/32] + … = \sum_{n = 0}^{[log_4(N/2)]}[N/(2*4^n)]
здесь [ ] — целая часть числа.

Последний раз редактировалось 404; 04.02.2009 в 12:41.
404 вне форума  
Конфигурация ПК
Ответить с цитированием
Непрочитано 11.02.2009, 14:05   [включить плавающее окно]   #7
dark_rex
Мужской Бывалый
 
Регистрация: 05.10.2006
Цитата (404) »
Цитата (dark_rex) »
а если рекурсией пока количество двукратных чисел не станет равным нулю?
А более конкретно это как?
Ну, при наличии двукратного числа мы обязательно получим остаток от деления 0 (деление чисел самих на себя легко отловить). Если получаем такой результат, то подкручиваем спецсчетчик, например g. Ну а во внешний цикл while ставим условие что, повторять пока этот счетчик g != 0. (Сначала хотел написать об использовании двух вложенных друг в друга циклов for с выходом по break (проверка if), но данный код будет работать только с числами до 10, т.е. его нельзя будет масштабировать.

Цитата
Решение. Рассмотрим все возможные последовательности из чисел от 1 до N, удовлетворяющие условию задачи, т. е. не содержащие чисел, отличающихся ровно в 2 раза.
...........
Большое спасибо!
dark_rex вне форума  
Ответить с цитированием
Непрочитано 11.02.2009, 16:58   [включить плавающее окно]   #8
404
Мужской Умудрённый
 
Регистрация: 04.08.2003
Цитата (dark_rex) »
Большое спасибо!
Пожалуйста. Там в доказательстве только небольшой недочёт, должно быть:
Цитата (404) »
Cнизу эта цепочка может быть органичена числом C*2, сверху — N.
404 вне форума  
Конфигурация ПК
Ответить с цитированием
Ответ Создать новую тему

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход


Текущее время: 21:33. Часовой пояс GMT +3.


Powered by vBulletin® Version 3.8.4
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot
Copyright © 2000-2017 3DNews. All Rights Reserved.
Администрация 3DNews требует соблюдения на форуме правил и законов РФ
Серверы размещены в Hostkey