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

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 01.02.2011, 21:49   #21
Smitt&Wesson
Профессионал
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Адрес: г. Киров
Сообщений: 13,937
Репутация: 815

skype: forwardbiznes
По умолчанию

Тут наблюдается определённая закономерность с единицей в старшем разряде (пока не пойму какая).

0-9 = 1
10-99 = 19
(100-119) = 32 + (120-199) = 16
200-999 = 20 * 8 (8 диапазонов).

заметно, что 1-а (или её отсутствие) в старшем разряде сильно влияет на цикличность суммы.
Дальше пока не разобрался.

Цитата:
Сообщение от Obey-Kun Посмотреть сообщение
имелось в виду, что из 15 надо сделать strin 151413121110987654321 и посчитать кол-вол единиц, но это не вариант, ибо как оказалось, надо не единицы считать, а числа с как минимум одной единицей
Ваш способ верен, в числе 15 действительно 8 единичек, но для числа 10^9, никакой оперативки не хватит. Имеется ввиду применение вычислительных методов.
Можно поступить так.
Каждое число переводить в string и подсчитывать 1-и, но для числа 10^9, это будет очень долгий процесс.
__________________
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder

Последний раз редактировалось Smitt&Wesson; 01.02.2011 в 22:39.
Smitt&Wesson вне форума   Ответить с цитированием
Старый 01.02.2011, 22:17   #22
Акоб
Форумчанин
 
Регистрация: 10.01.2011
Сообщений: 243
Репутация: 14
По умолчанию

Код:
можно написать генератор 
for(int i = 0; i <=9; i++)
    {
      if(i == 1)
         n++; 
    for(int j = 0; j <= 9; j++)
       {
           if(j == 1)
              n++;     
        for(int k = 0; k <= 9; k++)
            {
               if(k == 1)
                  n++;  
            for(int c = 0;c <= 9; c++)
                 {
                   if(c == 1)
                      n++;
                    if(i*1000 +j*100 +k*10 + c == N)
                      {
                          cout<<n<<endl;  
                         return 0;
                      }        
                 }
             }
        }
     }

Последний раз редактировалось Акоб; 01.02.2011 в 22:19.
Акоб вне форума   Ответить с цитированием
Старый 01.02.2011, 22:25   #23
Smitt&Wesson
Профессионал
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Адрес: г. Киров
Сообщений: 13,937
Репутация: 815

skype: forwardbiznes
По умолчанию

Цитата:
Сообщение от Акоб Посмотреть сообщение
можно написать генератор
Можно и так, но для числа 10^9, придётся писать 10 вложенных циклов. Вы часом не из Индии .
__________________
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder

Последний раз редактировалось Smitt&Wesson; 01.02.2011 в 22:29.
Smitt&Wesson вне форума   Ответить с цитированием
Старый 01.02.2011, 22:34   #24
Акоб
Форумчанин
 
Регистрация: 10.01.2011
Сообщений: 243
Репутация: 14
По умолчанию

написть цикл каторый я предложил для 10^4 и найти алгоритм.
нет не из Идии
из Армении
где сам автор?
Акоб вне форума   Ответить с цитированием
Старый 01.02.2011, 22:42   #25
Smitt&Wesson
Профессионал
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Адрес: г. Киров
Сообщений: 13,937
Репутация: 815

skype: forwardbiznes
По умолчанию

Цитата:
Сообщение от Акоб Посмотреть сообщение
написть цикл каторый я предложил для 10^4 и найти алгоритм.
нет не из Идии
из Армении
где сам автор?
Ну, до 1000, я и так разобрался. Весь вопрос в общем алгоритме. И доказательстве его правильности для любого, произвольно взятого, диапазона чисел.
Автор пропал куда-то. Испугался собственной темы .
__________________
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума   Ответить с цитированием
Старый 01.02.2011, 22:42   #26
NiCola999
Не
Профессионал
 
Регистрация: 29.10.2009
Адрес: Москва
Сообщений: 1,456
Репутация: 159

icq: 458-666-144
По умолчанию

Цитата:
Вы часом не из Индии
.
NiCola999 вне форума   Ответить с цитированием
Старый 01.02.2011, 22:44   #27
Акоб
Форумчанин
 
Регистрация: 10.01.2011
Сообщений: 243
Репутация: 14
По умолчанию

и до чего же дошел?
Акоб вне форума   Ответить с цитированием
Старый 01.02.2011, 22:50   #28
boomeer
Форумчанин
 
Аватар для boomeer
 
Регистрация: 04.08.2010
Сообщений: 110
Репутация: 11
По умолчанию

Цитата:
Сообщение от Smitt&Wesson Посмотреть сообщение
Ну, до 1000, я и так разобрался. Весь вопрос в общем алгоритме. И доказательстве его правильности для любого, произвольно взятого, диапазона чисел.
Автор пропал куда-то. Испугался собственной темы .
Тут я. Но последний раз за сегодня =)
Придумал такое решение.
От каждой цифры числа, кроме числа единиц, которая больше 1 отнимаем 1. Умножаем это число на 9. Складываем все + число единиц числа. Теперь от n+1 отнимем это число. Вуаля.
n=29 таким образом 1*9 + 9 = 18. Вычтите из n+1, и получаем 12
5394=9*9*9*4+2*9*9+8*9+4=5395-3154=2241
для 100: 1*9*9=81; 101-81=20
Писал сумбурно, если что завтра поясню как решал)
boomeer вне форума   Ответить с цитированием
Старый 01.02.2011, 23:00   #29
Obey-Kun
Линуксоид
Профессионал
 
Аватар для Obey-Kun
 
Регистрация: 31.07.2009
Адрес: Москва
Сообщений: 1,403
Репутация: 165

icq: 323216
По умолчанию

Вот в лоб. У меня для 1234512345 оно 45 секунд считает.
Код:
#include <iostream>

inline bool valueContainsOne(int n)
{
    do {
        if (n % 10 == 1) {
            return true;
        }
    } while (n /= 10);
    return false;
}

int main()
{
    int x;
    do {
        std::cout << "Enter fucking positive number: ";
        std::cin >> x;
    } while (x < 1);
    int result = 0;
    for (; x >= 1; --x) {
        if (valueContainsOne(x)) {
            ++result;
        }
    }
    std::cout << "Your answer is " << result << ", dumbass." << std::endl;
}
Можно распараллелить по процессорам при помощи OpenMP (+ 3 строчки к исходникам) или считать средствами видеокарты :D.
__________________
Я схожу с ума или это глючит реальность?
Jabber ID: obey@obey.su

Последний раз редактировалось Obey-Kun; 01.02.2011 в 23:23.
Obey-Kun вне форума   Ответить с цитированием
Старый 01.02.2011, 23:08   #30
NiCola999
Не
Профессионал
 
Регистрация: 29.10.2009
Адрес: Москва
Сообщений: 1,456
Репутация: 159

icq: 458-666-144
По умолчанию

да нет в лоб хреново будет, но всё-таки: =))
Код:
#include <stdio.h>

int isOnes(int n){
    for(;n > 0; n/=10){
            if(n%10 == 1) return 1;
    }
    return 0;
}

int main(void){
    
    int i, sum = 0;
    for(i=1; i<=1000000000; i++) sum += isOnes(i);
    printf("%d\n", sum);
    return 0;
}
Код:
612579512

real	1m3.078s
user	0m57.632s
sys	0m1.508s
NiCola999 вне форума   Ответить с цитированием
Ответ

Опции темы

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

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

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

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
подсчитать количество слов, в которые входит символ "е" Zhasik Паскаль 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


03:02.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.