Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Visual C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 01.02.2011, 18:03   #1
boomeer
Форумчанин
 
Аватар для boomeer
 
Регистрация: 04.08.2010
Сообщений: 110
По умолчанию Количество "единичек"

Вводится число n. Нужно определить сколько "единичек" в отрезке [1..n]
Например для 10 это 2, для 50 - 14.
Похоже на довольно стандартную задачу, но как сделать не пойму...
N может достигать 10^9
Пытался вывести формулу, но что то никак.
Можно динамикой предподсчитать сколько единичек от 1 до 10^k. Считаем сколько получилось на 10^(k-1), для 10^k очевидно ответ 10^(k-1)+то что было раньше(берется из соображения что мы можем после каждого числа поставить 0,1,2,3,4,5,6,7,8,9) Далее разбиваем свой отрезок от L до R на 2 части-от 1 до L и от 1 до R. Далее у нас сохраняется динамика, допустим у нас число L...равно 212344587. Берем и считаем ответ от 1 до 200000000, потом от 200000000 до 210000000 и тд

Под "единичками" имеется в виду числа, содержащие единички.

Последний раз редактировалось boomeer; 01.02.2011 в 21:19.
boomeer вне форума Ответить с цитированием
Старый 01.02.2011, 18:18   #2
Obey-Kun
Линуксоид
Участник клуба
 
Аватар для Obey-Kun
 
Регистрация: 31.07.2009
Сообщений: 1,403
По умолчанию

1. Делаешь функцию int numberOfOnes(int x), возвращающую кол-во единичек в числе x.
2. Прогоняешь цикл: for(;n>=1;--n){ sum_of_ones += numberOfOnes(n); }
3. ?????
4. PROFIT!
Я схожу с ума или это глючит реальность?
Jabber ID: obey@obey.su
Obey-Kun вне форума Ответить с цитированием
Старый 01.02.2011, 18:25   #3
NiCola999
Не
Участник клуба
 
Регистрация: 29.10.2009
Сообщений: 1,456
По умолчанию

Цитата:
для 10 это 2, для 50 - 14.
что-то я не понял, можете привести пример

как понять от 1 до 10 2 единицы
NiCola999 вне форума Ответить с цитированием
Старый 01.02.2011, 18:27   #4
Obey-Kun
Линуксоид
Участник клуба
 
Аватар для Obey-Kun
 
Регистрация: 31.07.2009
Сообщений: 1,403
По умолчанию

1 ← 1 единица
2
3
4
5
6
7
8
9
10 ← 1 единица

от 1 до 10 две единицы.
Я схожу с ума или это глючит реальность?
Jabber ID: obey@obey.su

Последний раз редактировалось Obey-Kun; 01.02.2011 в 18:29.
Obey-Kun вне форума Ответить с цитированием
Старый 01.02.2011, 18:29   #5
NiCola999
Не
Участник клуба
 
Регистрация: 29.10.2009
Сообщений: 1,456
По умолчанию

понятно )

Цитата:
Делаешь функцию int numberOfOnes(int x), возвращающую кол-во единичек в числе x.
хехе, прикинь сколько цикл будет работать при n = 10^9
надо что-то похитрее...

кстати для 50 не 14, а 15

Последний раз редактировалось Stilet; 03.02.2011 в 19:22.
NiCola999 вне форума Ответить с цитированием
Старый 01.02.2011, 20:00   #6
Obey-Kun
Линуксоид
Участник клуба
 
Аватар для Obey-Kun
 
Регистрация: 31.07.2009
Сообщений: 1,403
По умолчанию

Тогда можно формулу вывести, ничего сложного по идее.
Я схожу с ума или это глючит реальность?
Jabber ID: obey@obey.su
Obey-Kun вне форума Ответить с цитированием
Старый 01.02.2011, 20:14   #7
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,951
По умолчанию

Задачка довольно простая.

1. берём число (для простоты от 0 до n)
2. делаем целочисленное деление командой div
3. во внутреннем цикле подсчитываем количество единиц в остатке
4. так повторяем до n = 0

Для числа 10^9 получим 9-ть внешних циклов и по 10 внутренних на какждую итерацию.
Итого 9*10=90 циклов!
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 01.02.2011, 20:19   #8
boomeer
Форумчанин
 
Аватар для boomeer
 
Регистрация: 04.08.2010
Сообщений: 110
По умолчанию

Цитата:
Сообщение от Obey-Kun Посмотреть сообщение
Тогда можно формулу вывести, ничего сложного по идее.
Пробовал я пробовал вывести формулу, доказать индукцией... И фиг
boomeer вне форума Ответить с цитированием
Старый 01.02.2011, 20:40   #9
NiCola999
Не
Участник клуба
 
Регистрация: 29.10.2009
Сообщений: 1,456
По умолчанию

какие 90 итераций? считовод вотруба

внешний 10^9 итераций + внутренний от 1 до 9 итераций, сложность O(n)
NiCola999 вне форума Ответить с цитированием
Старый 01.02.2011, 20:46   #10
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,951
По умолчанию

Поспешил я с алгоритмом. С лёту не удаётся сделать .

Цитата:
Сообщение от NiCola999 Посмотреть сообщение
какие 90 итераций? считовод вотруба

внешний 10^9 итераций + внутренний от 1 до 9 итераций, сложность O(n)
Но-но, полегче. Алгоритм верен отчасти. Решу - покажу.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder

Последний раз редактировалось Smitt&Wesson; 01.02.2011 в 20:52.
Smitt&Wesson вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
подсчитать количество слов, в которые входит символ "е" Zhasik Паскаль, Turbo Pascal, PascalABC.NET 3 27.12.2010 11:29
Подсчитать количество букв "А" в предложении и общее количество букв.В тексте из файла несколько строк. kvas91 Общие вопросы C/C++ 3 14.11.2010 17:51
Как обойти "преобразование типа из "string" в "float" невозможно" lexluter1988 Помощь студентам 1 07.08.2010 12:23
при вводе на листе "магазин"- код товара появлялось "описание" товара из "склада" с "продажной ценой" aleksei78 Microsoft Office Excel 13 25.08.2009 12:04