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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.73
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
26.07.2013, 16:54     Задача "Натуральный ряд чисел" #1
(Время: 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++ "НОК трех чисел" и "Площадь треугольника"
C++ Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64"
C++ В этой программе создается "матрица" из секунд.Как мне первый ряд чисел (секунд) присвоить масиву?
C++ Существует ряд чисел. Вместо "?" вставить символы
C++ Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
27.07.2013, 18:44     Задача "Натуральный ряд чисел" #21
Цитата Сообщение от Thinker Посмотреть сообщение
смысл начинать объяснять то, на что банально сил не хватает...
Там все то-же, что и для двухзначных, только условий в три раза больше будет. Если разобраться с подходом в двухзначным, то трехзначные не проблема.
Я лишь предложил идею, если ТС нужно, то он сам дальше разберется. Вся соль там в записи одного уравнения и одного неравенства, а дальше просто разбор случаев.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 18:48     Задача "Натуральный ряд чисел" #22
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Там все то-же, что и для двухзначных, только условий в три раза больше будет.
сложного в этой задаче ничего нет. надо только рассмотреть 9 граничных случаев для 1,2,3-значных чисел, ну а потом проверки в отдельных группах чисел. просто условия надо писать аккуратно и аккуратно вычислять позицию числа. так как это делать никому не хочется (скукатище), поэтому легче рассмотреть вариант от Dani
alsav22
5282 / 4801 / 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
5282 / 4801 / 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
5282 / 4801 / 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
Модератор
 Аватар для Catstail
21504 / 10257 / 1670
Регистрация: 12.02.2012
Сообщений: 17,145
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
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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, можно, я просто по условию делал
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
28.07.2013, 14:26     Задача "Натуральный ряд чисел" #30
Catstail, даже если решать задачу влоб, то памяти хватит более чем на 5000 полностью сгенерированных последовательностей... Так что за памятью тут дело не стоит, зачем так много выделили на задачу?
Catstail
Модератор
 Аватар для Catstail
21504 / 10257 / 1670
Регистрация: 12.02.2012
Сообщений: 17,145
28.07.2013, 14:39     Задача "Натуральный ряд чисел" #31
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Epic fail - не работает!
- я исправлю... Торопился.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
что ты вообще понимаешь под "практической"?
- применительно к данному разделу, это алгоритм (или структура данных), которая используется в расхожих повседневных задачах (списки, стеки, очереди, сортировки, поиск, и т.п.)
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
28.07.2013, 15:50     Задача "Натуральный ряд чисел" #32
и еще один вариант
генерирует строку пока не найдет заданное число
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
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
 
int match(int x)
{
    std::string buf;
    std::string x_str = std::to_string(x);
    int digits = std::log10(x) + 1;
    int number_match = 0;
 
    if (x < 1 || x >= 10000) {
        return 38885;
    }
 
    for (int i = 1; i <= x; ++i) {
        for (int j = 0; j != digits; ++j) {
            buf.append( std::to_string(i++) );
        }
        --i;
        number_match = buf.find(x_str, number_match);
        if (number_match == std::string::npos) {
            number_match = buf.size() - digits;
        } else {
            return number_match + 1;
        }
    }
    return 1;
}
 
int main()
{
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
    if (!in.good() || !out.good())
        return 1;
    int x; in >> x;
    out << match(x);
    out.close();
    return 0;
}
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
28.07.2013, 16:53     Задача "Натуральный ряд чисел" #33
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int x;
    scanf("%d", &x);
 
    char str[40000] = {'\0'};
    char buf[26] = {'\0'};
    char number[6] = {'\0'};
    char numbuf[6] = {'\0'};
 
    itoa(x, number, 10);
 
    int digits = strlen(number);
    int i, j, continue_from = 0;
 
    for (i = 1; i <= x; ++i) {
        buf[0] = '\0';
        for(j = 0; j < digits; ++j, ++i) {
            strcat( buf, itoa(i, numbuf, 10) );
        }
        strcat( str, buf );
        --i;
        char *match = strstr(str + continue_from, number);
        if (match == NULL) {
            continue_from = strlen(str) - digits;
        } else {
            printf("%d", match - str + 1);
            return 0;
        }
    }
    return 0;
}
Миниатюры
Задача "Натуральный ряд чисел"  
Catstail
Модератор
 Аватар для Catstail
21504 / 10257 / 1670
Регистрация: 12.02.2012
Сообщений: 17,145
28.07.2013, 17:11     Задача "Натуральный ряд чисел" #34
Вот решение без строк, без доп. функций и т.п. - "ручками":

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
63
64
65
66
67
68
69
70
71
#include <iostream.h>
 
int SCurr=1,Pos=1;
int Arr[10],Ptr=0;
int Counter=0;
 
int NextDigit()
{
    int i,r,c;
    Pos++;
    Counter++;
    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,j,p,N,c,r,q;
    int digs[4],cadr[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;
    }
 
    for (i=0; i<p; i++)
        cadr[i]=NextDigit();
 
    while (Counter <= 2147483647)
    {
        q=0;
        for (j=0; j<p; j++)
            if (digs[p-j-1] != cadr[j])
            {
                q=-1;
                break;
            }
        if (q == 0)
        {
            cout << "Pos=" << (Pos-p) << endl;
            break;
        }
        else
        {
            for (j=0; j<p-1; j++) cadr[j]=cadr[j+1];
            cadr[p-1]=NextDigit();
        }
    }
    return 0;
}
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
28.07.2013, 17:17     Задача "Натуральный ряд чисел" #35
Catstail, 19-й тест не проходит(
Миниатюры
Задача "Натуральный ряд чисел"  
Catstail
Модератор
 Аватар для Catstail
21504 / 10257 / 1670
Регистрация: 12.02.2012
Сообщений: 17,145
28.07.2013, 17:20     Задача "Натуральный ряд чисел" #36
Да я не собирался тестировать на сайте... Мне было интересно решить задачу без строк и без библиотек. А что там в "19-м" тесте? Какое-то число не находит?
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
28.07.2013, 17:22     Задача "Натуральный ряд чисел" #37
Catstail, выдает неверный ответ. Входные данные известны только для первых трёх тестов...
Catstail
Модератор
 Аватар для Catstail
21504 / 10257 / 1670
Регистрация: 12.02.2012
Сообщений: 17,145
28.07.2013, 17:23     Задача "Натуральный ряд чисел" #38
Olivеr, можешь привести эти три теста?
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
28.07.2013, 17:27     Задача "Натуральный ряд чисел" #39
Catstail,
INPUT.TXTOUTPUT.TXT
1454
210110
314273
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2013, 17:29     Задача "Натуральный ряд чисел"
Еще ссылки по теме:

Классы "Пара чисел" и "Прямоугольный треугольник" C++
Классы "Пара чисел" и "Прямоугольный треугольник" C++
C++ Создать список из целых чисел. После каждого элемента, равного "х" вставить элемент, равный "у"

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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21504 / 10257 / 1670
Регистрация: 12.02.2012
Сообщений: 17,145
28.07.2013, 17:29     Задача "Натуральный ряд чисел" #40
Спасибо, все проходит.
Yandex
Объявления
28.07.2013, 17:29     Задача "Натуральный ряд чисел"
Ответ Создать тему
Опции темы

Текущее время: 10:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru