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

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

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

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

26.07.2013, 16:54. Просмотров 3590. Ответов 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; (натуральный логарифм), но не знаю с чего начать и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
0
Thinker
Эксперт C++
4226 / 2200 / 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. задание внимательно прочтите.
1
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
27.07.2013, 18:09 #18
Цитата Сообщение от Thinker Посмотреть сообщение
101 - ответ 10. задание внимательно прочтите.
так вот в чем дело...
0
nonedark2008
909 / 648 / 134
Регистрация: 28.07.2012
Сообщений: 1,760
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.
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 18:33 #20
nonedark2008, это все давно уже поняли.

Цитата Сообщение от nonedark2008 Посмотреть сообщение
мне лень
смысл начинать объяснять то, на что банально сил не хватает...
0
nonedark2008
909 / 648 / 134
Регистрация: 28.07.2012
Сообщений: 1,760
27.07.2013, 18:44 #21
Цитата Сообщение от Thinker Посмотреть сообщение
смысл начинать объяснять то, на что банально сил не хватает...
Там все то-же, что и для двухзначных, только условий в три раза больше будет. Если разобраться с подходом в двухзначным, то трехзначные не проблема.
Я лишь предложил идею, если ТС нужно, то он сам дальше разберется. Вся соль там в записи одного уравнения и одного неравенства, а дальше просто разбор случаев.
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 18:48 #22
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Там все то-же, что и для двухзначных, только условий в три раза больше будет.
сложного в этой задаче ничего нет. надо только рассмотреть 9 граничных случаев для 1,2,3-значных чисел, ну а потом проверки в отдельных группах чисел. просто условия надо писать аккуратно и аккуратно вычислять позицию числа. так как это делать никому не хочется (скукатище), поэтому легче рассмотреть вариант от Dani
0
alsav22
5420 / 4816 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
27.07.2013, 20:14 #23
Цитата Сообщение от Olivеr Посмотреть сообщение
так вот в чем дело...
Цитата Сообщение от Thinker Посмотреть сообщение
надо только рассмотреть 9 граничных случаев для 1,2,3-значных чисел
Может быть, например, ещё такое: 123. Выдаст 259, правильный ответ: 1.
0
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; //позиция, начиная с которой в строке записано первое вхождение заданного числа.
                                                //Нумерация позиций начинается с единицы.
 
}
0
alsav22
5420 / 4816 / 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;
}
Вот это и есть позиция?
0
Миниатюры
Задача "Натуральный ряд чисел"  
alsav22
5420 / 4816 / 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;
}
0
Catstail
Модератор
22619 / 10980 / 1779
Регистрация: 12.02.2012
Сообщений: 18,123
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;
}
1
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
28.07.2013, 11:44 #28
Catstail, Epic fail - не работает!
проверка 1121 - вывод 226
ожидание 13е место
т.к. ряд 12345678910111213

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

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

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

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

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


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

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

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