Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.73
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

Задача "Натуральный ряд чисел" - C++

26.07.2013, 16:54. Просмотров 3539. Ответов 70
Метки нет (Все метки)

(Время: 1 сек. Память: 16 Мб)
Натуральные числа записаны в строку без каких-либо разделителей. Начало этой строки имеет вид 123456789101112131415161718192021… .

Требуется написать программу, которая определит первое вхождение десятичной записи заданного числа N в этой строке.

Входные данные

Входной файл INPUT.TXT содержит заданное число N (1 <= N <= 104).

Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно число – позицию, начиная с которой в строке записано первое вхождение заданного числа. Нумерация позиций начинается с единицы.

Предложите свои идеи по решению задачи.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.07.2013, 16:54     Задача "Натуральный ряд чисел"
Посмотрите здесь:

Существует ряд чисел. Вместо "?" вставить символы - C++
Пожалуйста помогите дали задачу по циклам решить не могу. вот условие : существует ряд чисел ((((1?2)?3)?4)?5)?6 который равен 35 ; ...

Вывести на экран с точностью два знака число "е" (натуральный логарифм) - C++
Всем привет! Нужно написать программку на вывод на экран с точностью два знака число &quot;е&quot; (натуральный логарифм), но не знаю с чего начать и...

В этой программе создается "матрица" из секунд.Как мне первый ряд чисел (секунд) присвоить масиву? - C++
//--------------------------------------------------------------------------- #include &lt;vcl.h&gt; #pragma hdrstop #include...

"НОК трех чисел" и "Площадь треугольника" - C++
Помогите пожалуйста решить 2 задачи. 1. Разработать функцию, возвращающую наименьшее общее кратное трёх заданных натуральных чисел. 2....

Ошибка "stack overflow". Разложение функции в ряд Тейлора - C++
Задание: рекурентно реализовать разложение ф-ии {\sin}^{2} по ряду Тэйлора. Выдает ошибку &quot;Необработанное исключение в &quot;0x00cc18a9&quot; в...

"Вычисление функций с использованием их разложения в степенной ряд" - C++
Цель: Практика в организации итерационных и арифметических циклов, использование функций. Постановка задачи Для х изменяющегося от...

Натуральный ряд - C++
Еще вопрос:&quot;Сколько чисел натурального ряда необходимо перемножить, чтобы их произведение превысило заданное натуральное число.&quot; ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
27.07.2013, 17:38     Задача "Натуральный ряд чисел" #16
Цитата Сообщение от Thinker Посмотреть сообщение
не все так просто, протестируйте, например, на 101
ответ 193
число 101 включает 9 однозначных чисел (9 символов), 90 двузначных (180 символов) и 1 трехзначное (3 символа) + 1 = 193
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 17:39     Задача "Натуральный ряд чисел" #17
Цитата Сообщение от Olivеr Посмотреть сообщение
ответ 193
число 101 включает 9 однозначных чисел (9 символов), 90 двузначных (180 символов) и 1 трехзначное (3 символа) + 1 = 193
101 - ответ 10. задание внимательно прочтите.
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
27.07.2013, 18:09     Задача "Натуральный ряд чисел" #18
Цитата Сообщение от Thinker Посмотреть сообщение
101 - ответ 10. задание внимательно прочтите.
так вот в чем дело...
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
27.07.2013, 18:27     Задача "Натуральный ряд чисел" #19
Если число однозначное - все просто.
Если двухзначное:
--Если вторая цифра минус первая = 1, то число встречается среди первых 9 однозначных.
-- Если расмотреть стык aX Yb, то если X = 9, то a = Y - 1, b = 0. Если X != 9, то такое совпадение будет только если Y <= X. Тогда a = Y, b = X + 1.
-- Ну а в противном случае число появится в последовательности только когда его туда напишут.
Для трехзначных можно запилить что-то схожее, но мне лень, там много больше случаев разбирать.

Добавлено через 7 минут
Ну еще для двухзначных нужно не забыть про стык однозначных и двухзначных, там тоже проскакивает число 91.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 18:33     Задача "Натуральный ряд чисел" #20
nonedark2008, это все давно уже поняли.

Цитата Сообщение от nonedark2008 Посмотреть сообщение
мне лень
смысл начинать объяснять то, на что банально сил не хватает...
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
27.07.2013, 18:44     Задача "Натуральный ряд чисел" #21
Цитата Сообщение от Thinker Посмотреть сообщение
смысл начинать объяснять то, на что банально сил не хватает...
Там все то-же, что и для двухзначных, только условий в три раза больше будет. Если разобраться с подходом в двухзначным, то трехзначные не проблема.
Я лишь предложил идею, если ТС нужно, то он сам дальше разберется. Вся соль там в записи одного уравнения и одного неравенства, а дальше просто разбор случаев.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 18:48     Задача "Натуральный ряд чисел" #22
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Там все то-же, что и для двухзначных, только условий в три раза больше будет.
сложного в этой задаче ничего нет. надо только рассмотреть 9 граничных случаев для 1,2,3-значных чисел, ну а потом проверки в отдельных группах чисел. просто условия надо писать аккуратно и аккуратно вычислять позицию числа. так как это делать никому не хочется (скукатище), поэтому легче рассмотреть вариант от Dani
alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
27.07.2013, 20:14     Задача "Натуральный ряд чисел" #23
Цитата Сообщение от Olivеr Посмотреть сообщение
так вот в чем дело...
Цитата Сообщение от Thinker Посмотреть сообщение
надо только рассмотреть 9 граничных случаев для 1,2,3-значных чисел
Может быть, например, ещё такое: 123. Выдаст 259, правильный ответ: 1.
fan_stud
0 / 0 / 0
Регистрация: 17.04.2013
Сообщений: 5
28.07.2013, 00:58     Задача "Натуральный ряд чисел" #24
Kuzia domovenok, сначала не понял, переделал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <fstream>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
 
using namespace std;
 
//перевод числа в строку
class format
{
    static std::ostringstream oss;
public:
    template <class T>
    static std::string to_string(const T &numeric_value)
    {
        format::oss.str("");
        format::oss.clear();
        format::oss << numeric_value;
        return oss.str();
    }
};
 
ostringstream format::oss;
 
int main()
{
    string str;
    unsigned N; //заданное число
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    fin >> N;
    for (int i = 1; i <= N; i++)
        str += format::to_string(i);
 
    cout << str;
    fout << str.find(format::to_string(N)) + 1; //позиция, начиная с которой в строке записано первое вхождение заданного числа.
                                                //Нумерация позиций начинается с единицы.
 
}
alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
28.07.2013, 01:14     Задача "Натуральный ряд чисел" #25
fan_stud, если так упростить, то нормально будет?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    string str;
    unsigned N = 123; //заданное число
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    //fin >> N;
    for (int i = 1; i <= N; i++)
        str += format::to_string(i);
 
    cout << str;
    cout << str.find(format::to_string(N)) + 1; //позиция, начиная с которой в строке записано первое вхождение заданного числа.
                                                //Нумерация позиций начинается с единицы.
    cout << endl;
    system("pause");
    return 0;
}
Вот это и есть позиция?
Миниатюры
Задача "Натуральный ряд чисел"  
alsav22
5416 / 4812 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
28.07.2013, 01:21     Задача "Натуральный ряд чисел" #26
Прошу прощения, одну вещь не сделал в коде, поэтому не понял вывод.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    string str;
    unsigned N = 123; //заданное число
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    //fin >> N;
    for (int i = 1; i <= N; i++)
        str += format::to_string(i);
 
    cout << str << endl;
    cout << str.find(format::to_string(N)) + 1; //позиция, начиная с которой в строке записано первое вхождение заданного числа.
                                                //Нумерация позиций начинается с единицы.
    cout << endl;
    system("pause");
    return 0;
}
Catstail
Модератор
22515 / 10920 / 1774
Регистрация: 12.02.2012
Сообщений: 18,067
28.07.2013, 11:20     Задача "Натуральный ряд чисел" #27
Судя по "высокой практической ценности", это типичная олимпиадная задача. Захотелось попробовать решить ее без привлечения строк. И вот что получилось (число вводится с клавиатуры; для сути алгоритма это совершенно неважно). Не уверен, что уложится в 1 сек, но вот по памяти уложится с гарантией.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream.h>
int SCurr=1,Pos=1;
int Arr[10],Ptr=0;
int NextDigit()
{
    int i,r,c;
    Pos++;
    if (Ptr == 0)
    {
        c=SCurr++;
        for (i=1; i<=10; i++) Arr[i]=0;
        for (i=1; i<=10; i++)
        {
            r=c % 10;
            Arr[Ptr++]=r;
            c=c / 10;
            if (c == 0) break;
        }
    }
    return Arr[--Ptr];
}
int main(int argc, char* argv[])
{
    int i,p,N,c,r,d,q;
    int digs[4];
    cout << "Enter number: ";
    cin >> N;
    c=N;
    p=0;
    for (i=1; i<=4; i++)
    {
        if (c==0) break;
        r=c % 10;
        digs[p++]=r;
        c=c / 10;
    }
    q=1;
    for (i=1; i < 2147483648; i++)
    {
        d=NextDigit();
        while(1)
        {
            if (d == digs[p-q])
            {       
                q++;
                if (q > p) break;
                d=NextDigit();
            }
            else
            {
                q=1;
                break;
            }
        }
        if (q > 1)
        {
            cout << Pos-q+1 << endl;
            break;
        }
    }
    return 0;
}
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
28.07.2013, 11:44     Задача "Натуральный ряд чисел" #28
Catstail, Epic fail - не работает!
проверка 1121 - вывод 226
ожидание 13е место
т.к. ряд 12345678910111213

Добавлено через 2 минуты
Цитата Сообщение от Catstail Посмотреть сообщение
Судя по "высокой практической ценности", это типичная олимпиадная задач
что не так с практической ценностью?
а) это раздел для начинающих и ты не найдёшь тут каких-то практических задач
б) что ты вообще понимаешь под "практической"?
fan_stud
0 / 0 / 0
Регистрация: 17.04.2013
Сообщений: 5
28.07.2013, 14:19     Задача "Натуральный ряд чисел" #29
alsav22, можно, я просто по условию делал
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2013, 14:26     Задача "Натуральный ряд чисел"
Еще ссылки по теме:

Консольная игра "3 в ряд" - C++
подскажите самый простой способ реализации этой игры в консоле или алгоритм подскажите ,буду благодарен )

Абстрактный класс "ряд" - C++
Выдет следующие ошибки: undefined reference to `typeinfo for row' undefined reference to `vtable for row' на строчке: ...

Задача решена только нужна "нитра" фишки по ускорению - C++
Задача такая, создать файл заданного размера к примеру 500 мегабайтов, в него на генерировать рандомно данные а потом их отсортировать в...

Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером - C++
Гигабашня — самое высокое и глубокое здание в Киберленде. В ней 17 777 777 777 этажей, пронумерованных от  - 8 888 888 888 до...

Вычислить значение суммы. Задача с использованием "длинной арифметики". - C++
Тема: «Задачи на длинную арифметику» Задача: Вычислить точное значение суммы 1^2 + 2^2 + 3^2 + ... + n^2 (n ≥ 20000). Пожалуйста,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
28.07.2013, 14:26     Задача "Натуральный ряд чисел" #30
Catstail, даже если решать задачу влоб, то памяти хватит более чем на 5000 полностью сгенерированных последовательностей... Так что за памятью тут дело не стоит, зачем так много выделили на задачу?
Yandex
Объявления
28.07.2013, 14:26     Задача "Натуральный ряд чисел"
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru