Помогите с Задачей по С++!!! Завтра защита а задача не сделана :(

Alex Buriy · 26.12.2008, 16:30

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

А в С++ я совсем не шарю!!!

помогите пожалуйста!!! Заранее Спасибо!!!

Какое максимальное колличество натуральных чисел от 1 до 10 можно выбрать чтобы среди них не было отличающихся в два раза!!!

dark_rex · 12.01.2009, 13:17

Я что-то сомневаюсь в способности защитить курсовой проект при неспособности решать задачи для тетьего класса. Правильный ответ: 1, 3, 4, 5, 7, 9, т.е. 6 чисел.
1) создаем и заполняем одномерный массив (вектор) числами от 1 до 10;
2) в цикле вида for (i=1, i<11, i++) делаем проверку на неравенство 2 результата от деления чисел друг на друга (нужно либо последовательно делить каждое число на каждое, либо попробовать опимизировать количество операций);
3) при неравенстве подкручиваем счетчик;
4) печатаем значение счетчика.

404 · 01.02.2009, 13:34

Цитата (dark_rex) »

в цикле вида for (i=1, i<11, i++) делаем проверку на неравенство 2 результата от деления чисел

Каких чисел? Вы озвучили только один параметр, i — количество чисел. Но нужно же перебрать все сочетания из i чисел для каждого i. Что уже не есть тривиально. "3-ий класс" тут, конечно, не при чём.

Вообще это олимпиадная задачка по математике, не по программированию (только диапазон дают больше, скажем, от 1 до 100, чтоб сразу отбросить попытки простого перебора всех сочетаний). Ответ — все числа вида С*4^n, где n >= 0, C — нечётное.

anonymouse · 01.02.2009, 17:10

лучше сапоги примерь, сходи на турник. Учиться дальше смысла нет, если ты элементарного не можешь сдать.

dark_rex · 04.02.2009, 00:03

Цитата (404) »

Цитата (dark_rex) »

в цикле вида for (i=1, i<11, i++) делаем проверку на неравенство 2 результата от деления чисел

Каких чисел? Вы озвучили только один параметр, i — количество чисел. Но нужно же перебрать все сочетания из i чисел для каждого i. Что уже не есть тривиально. "3-ий класс" тут, конечно, не при чём.

Хм, а если рекурсией пока количество двукратных чисел не станет равным нулю?

Цитата

Вообще это олимпиадная задачка по математике, не по программированию (только диапазон дают больше, скажем, от 1 до 100, чтоб сразу отбросить попытки простого перебора всех сочетаний). Ответ — все числа вида С*4^n, где n >= 0, C — нечётное.

А можно вывод данной формулы? Интересно, как его получили...

404 · 04.02.2009, 12:29

Цитата (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)]
здесь [ ] — целая часть числа.

dark_rex · 11.02.2009, 14:05

Цитата (404) »

Цитата (dark_rex) »

а если рекурсией пока количество двукратных чисел не станет равным нулю?

А более конкретно это как?

Ну, при наличии двукратного числа мы обязательно получим остаток от деления 0 (деление чисел самих на себя легко отловить). Если получаем такой результат, то подкручиваем спецсчетчик, например g. Ну а во внешний цикл while ставим условие что, повторять пока этот счетчик g != 0. (Сначала хотел написать об использовании двух вложенных друг в друга циклов for с выходом по break (проверка if), но данный код будет работать только с числами до 10, т.е. его нельзя будет масштабировать.

Цитата

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

Большое спасибо!

404 · 11.02.2009, 16:58

Цитата (dark_rex) »

Большое спасибо!

Пожалуйста. Там в доказательстве только небольшой недочёт, должно быть:

Цитата (404) »

Cнизу эта цепочка может быть органичена числом C*2, сверху — N.

01.02.2009, 17:10	[включить плавающее окно] #4
anonymouse Продвинутый Регистрация: 04.05.2008	лучше сапоги примерь, сходи на турник. Учиться дальше смысла нет, если ты элементарного не можешь сдать. __________________ анонимный анонимаус.

04.02.2009, 12:29	[включить плавающее окно] #6
404 Умудрённый Регистрация: 04.08.2003	Цитата (dark_rex) » а если рекурсией пока количество двукратных чисел не станет равным нулю? А более конкретно это как? Цитата (dark_rex) » можно вывод данной формулы? Задача. Какое максимальное колличество натуральных чисел от 1 до N можно выбрать, чтобы среди них не было отличающихся в два раза? Решение. Рассмотрим все возможные последовательности из чисел от 1 до N, удовлетворяющие условию задачи, т. е. не содержащие чисел, отличающихся ровно в 2 раза. Пусть некая послед-ть A содержит число C2^(2n + 1), где C — какое-то нечётное число, n ≥ 0. Тогда A не может также содержать C2^(2n), но может содержать C2^(2n – 1); но тогда A не может содержать C2^(2n – 2), но может C2^(2n – 3); и т. д… Аналогично в большую сторону: A не может содержать C2^(2n + 2), но может содержать C2^(2n + 3); и т. д. Итак: если некая послед-ть A содержит число C2^(2n + 1), то она также содержит цепочку чисел: C2^(2q + 1), C2^(2(q+1) + 1), …, C2^(2p + 1), где 0 ≤ q ≤ n ≤ p; или иначе её можно записать как: C4^q2, C4^(q+1)2, …, C4^p2. Cнизу эта цепочка может быть органичена числом 2, сверху — N. Тогда расмотрим послед-ть B, которая, вместо этой цепочки, содержит другую: C4^q, C4^(q+1), …, C4^p, где 0 ≤ q ≤ n ≤ p; а все остальные числа в B те же самые, что в A. Такая послед-ть B также удовлетворяет условию задачи. Но, кроме того: если число C4^(p+1) ≤ N, мы тоже можем включить его в посл-ть B, и такая послед-ть тоже будет удовлетворять условию задачи, но содержать на 1 число больше, чем A. Если же C4^(p+1) > N, то в B будет столько же чисел, сколько в A. Итого: для любой послед-ти A, удовлетворяющей условию задачи, и содержащий числа вида C4^n2, можно указать послед-ть B, также удовлетворяющюю условию задачи, но содержащюю только числа вида C4^n, причём количество чисел в B будет больше или равным, чем в A. А значит, послед-ть, удовлетворяющая условию задачи, и содержащая только числа вида C4^n и будет той, количество чисел в которой максимально. Ну и посчитаем количество Q чисел вида C4^n от 1 до N: Q = [N/2] + [N/8] + [N/32] + … = \sum_{n = 0}^{[log_4(N/2)]}[N/(24^n)] здесь [ ] — целая часть числа. Последний раз редактировалось 404; 04.02.2009 в 12:41.*

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

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) печатаем значение счетчика.

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 — нечётное.

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 — нечётное. А можно вывод данной формулы? Интересно, как его получили...

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 раза. ........... Большое спасибо!

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