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

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

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

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

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

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

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

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

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

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

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

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

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include &lt;iostream&gt; using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в &quot;0x76f015de&quot; в &quot;контрольная 1 задача 2.exe&quot;: 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

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

Создать класс комплексных чисел и ввести операции: "+", "-", "*", "/". - C++
пожалуйста-помогите написатьпрограмму!!! сижу на экзамене!!! вот само задание: создать класс комплексных чисел и ввести операции: &quot;+&quot;,...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Catstail
Модератор
22613 / 10974 / 1778
Регистрация: 12.02.2012
Сообщений: 18,108
28.07.2013, 14:39 #31
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Epic fail - не работает!
- я исправлю... Торопился.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
что ты вообще понимаешь под "практической"?
- применительно к данному разделу, это алгоритм (или структура данных), которая используется в расхожих повседневных задачах (списки, стеки, очереди, сортировки, поиск, и т.п.)
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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;
}
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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;
}
0
Миниатюры
Задача "Натуральный ряд чисел"  
Catstail
Модератор
22613 / 10974 / 1778
Регистрация: 12.02.2012
Сообщений: 18,108
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;
}
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
28.07.2013, 17:17 #35
Catstail, 19-й тест не проходит(
1
Миниатюры
Задача "Натуральный ряд чисел"  
Catstail
Модератор
22613 / 10974 / 1778
Регистрация: 12.02.2012
Сообщений: 18,108
28.07.2013, 17:20 #36
Да я не собирался тестировать на сайте... Мне было интересно решить задачу без строк и без библиотек. А что там в "19-м" тесте? Какое-то число не находит?
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
28.07.2013, 17:22 #37
Catstail, выдает неверный ответ. Входные данные известны только для первых трёх тестов...
0
Catstail
Модератор
22613 / 10974 / 1778
Регистрация: 12.02.2012
Сообщений: 18,108
28.07.2013, 17:23 #38
Olivеr, можешь привести эти три теста?
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
28.07.2013, 17:27 #39
Catstail,
INPUT.TXTOUTPUT.TXT
1454
210110
314273
1
Catstail
Модератор
22613 / 10974 / 1778
Регистрация: 12.02.2012
Сообщений: 18,108
28.07.2013, 17:29 #40
Спасибо, все проходит.
0
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.07.2013, 17:31 #41
Catstail, скомпонуйте свою программу с программой от Olivеr и для каждого числа от 1 до 10000 сравните результат
0
dr.curse
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
28.07.2013, 17:34 #42
вот мое решение если интересно
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char s[256],ss[4000000]="";
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n,i;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        itoa(i,s,10);
        strcat(ss,s);
    }
    printf("%d",strstr(ss,s)-ss+1);
    return 0;
}
0
nonedark2008
908 / 647 / 134
Регистрация: 28.07.2012
Сообщений: 1,760
28.07.2013, 19:20 #43
Я тут начал писать алгоритм, работающий за O(1). Но потом подумал, зачем оно надо? Памяти то 16МБ отведено, а этого вполне хватит, чтобы хранить результат для всех 10000 чисел. Так что можно самым тупым алгоритмом вначале все вычислить, занести в таблицу и готово...
0
dr.curse
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
28.07.2013, 19:29 #44
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Я тут начал писать алгоритм, работающий за O(1).
а можно примерный вид?
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
28.07.2013, 20:16 #45
Цитата Сообщение от Catstail Посмотреть сообщение
Судя по "высокой практической ценности", это типичная олимпиадная задача.
не надо, пожалуйста, вносить смуту в народные массы. в любом деле от задач "для начинающих" нет практической пользы.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2013, 20:16
Привет! Вот еще темы с ответами:

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

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.07.2013, 20:16
Ответ Создать тему
Опции темы

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