Форум программистов, компьютерный форум 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++ Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
26.07.2013, 17:00     Задача "Натуральный ряд чисел" #2
1) Сгенерируй строку со всей последовательностью этих чисел.
2) Найди нужное число в этой строке.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
26.07.2013, 17:33  [ТС]     Задача "Натуральный ряд чисел" #3
Цитата Сообщение от Dani Посмотреть сообщение
Сгенерируй строку со всей последовательностью этих чисел.
Сколько нужно генерировать чисел и приблизительно какой нужен размер массива?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
26.07.2013, 17:41     Задача "Натуральный ряд чисел" #4
Добавляй лучше в string последовательные числа, пока длина не станет больше 10^4 (как в условии - максимальное кол-во цифр). Найдешь, какое-то число, вот до него и добавляй, либо подсчитай на листике до какого числа нужно добавлять.
Вот ты узнал число, до которого нужно добавлять последовательные числа, чтобы длина получилась больше либо равна 10^4. Потом просто генеришь хоть куда последовательность.
fan_stud
0 / 0 / 0
Регистрация: 17.04.2013
Сообщений: 5
26.07.2013, 18:06     Задача "Натуральный ряд чисел" #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <fstream>
#include <string>
#include <iostream>
 
using namespace std;
 
int main()
{
    string str;
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    fin >> str;
    char value('8');
    size_t first_value_in_str(str.find_first_of(value) + 1);
    fout << first_value_in_str;
    return 0;
}
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
26.07.2013, 18:27  [ТС]     Задача "Натуральный ряд чисел" #6
fan_stud можете объяснить код?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.07.2013, 22:30     Задача "Натуральный ряд чисел" #7
Цитата Сообщение от Dani Посмотреть сообщение
Сгенерируй строку со всей последовательностью этих чисел.
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Сколько нужно генерировать чисел и приблизительно какой нужен размер массива?
9 + 2*90 + 3*900 + 4

Добавлено через 1 минуту
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
можете объяснить код?
ищется подстрока в строке, осталось сгенирировать саму строку
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
26.07.2013, 22:32     Задача "Натуральный ряд чисел" #8
ALEXKIRNAS, fan_stud не понял условия задачи по ходу.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.07.2013, 12:31     Задача "Натуральный ряд чисел" #9
fan_stud, ерунда какая-то. Во-первых, в файле INPUT.TXT этой строки нету, а ты решил просто взять и сделать "fin >> str;"
Во-вторых, эту задачу не надо решать в лоб.
Число N четырёхзначное.
Так надо проанализировать, в каких случаях это число может стать подстрокой.
Ну, например: если цифры идут по порядку - число из первого десятка. (6789) =6,7,8,9
далее проверять случаи, когда это два двузначных числа (1011) = 10, 11
одно двузначное и начальные цифры от следующего за и перед ним (6373) =36, 37,38
аналогично - трёхзначные (5645) = 564, 565
аналогично - соседние четырёхзначные (9992)= 1999, 2000
Ну и, наконец, это самостоятеельное четырёхзначное число 1991
(возможно пропустил какой-то случай, например на границе двузначных и трёхзначных и.т.п.)

Вот и построй условия для каждого из этих случаев. А потом, найди, какой из них раньше встречается.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
27.07.2013, 13:31     Задача "Натуральный ряд чисел" #10
Kuzia domovenok, число N может быть и однозначным и двухзначным и трехзначным. Слишком много условий выходит. А так подход верный, только слишком много вариантов нужно разобрать, можно что-то и упустить.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
27.07.2013, 15:27     Задача "Натуральный ряд чисел" #11
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Так надо проанализировать, в каких случаях это число может стать подстрокой
По-моему, в любом случае, при достаточной длине исходной строки. Вот об этом ничего не сказано.

Добавлено через 6 минут
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
#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
 
 
int main()
{    
    string str;
    string number = "28";
    string temp;
    stringstream s;
    int i = 1;
    do
    {
      s << i;
      temp = s.str();
      s.str("");
      str += temp;
      cout << str << endl;
      ++i;
    } while (temp != number);
    int ind = str.size() - temp.size() + 1;
    cout << ind << endl;
 
    system("pause");
    return(0);
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.07.2013, 15:36     Задача "Натуральный ряд чисел" #12
Цитата Сообщение от alsav22 Посмотреть сообщение
По-моему, в любом случае, при достаточной длине исходной строки.
Суть не в том, что появится число в строке или нет! Ясно, что появится.
А суть в том, что рассматривать надо не всю строку, а генерировать те подстроки, в которых может появиться это число!
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
27.07.2013, 16:15     Задача "Натуральный ряд чисел" #13
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А суть в том, что рассматривать надо не всю строку
А какая она вся? Она, вообще, задаётся как-то?

Добавлено через 6 минут
Как вариант, вывести формулу длины строки с заданной последовательностью, по заданному числу. Например, число 28, длина строки, с заданной последавательностью, 47. Дальше просто.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.07.2013, 17:26     Задача "Натуральный ряд чисел" #14
вот что получилось
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
#include <iostream>
#include <fstream>
#include <cmath>
 
int main()
{
    std::ifstream file("input.txt");
    std::ofstream out("output.txt");
    int x; file >> x;
    int rank = std::log10(x) + 1;
    int result = 1;
    switch (rank) {
        case 1:
            result = x;
            break;
        case 2:
            result = 9 + 2 * (x - 10) + 1;
            break;
        case 3:
            result = 9 + 180 + 3 * (x - 100) + 1;
            break;
        case 4:
            result = 9 + 180 + 2700 + 4 * (x - 1000) + 1;
            break;
        case 5:
            result = 9 + 180 + 2700 + 36000 + 1 - 5;
            break;
    }
    out << result;
    return 0;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.07.2013, 17:34     Задача "Натуральный ряд чисел" #15
Цитата Сообщение от Olivеr Посмотреть сообщение
вот что получилось
не все так просто, протестируйте, например, на 101
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.07.2013, 17:38     Задача "Натуральный ряд чисел" #16
Цитата Сообщение от Thinker Посмотреть сообщение
не все так просто, протестируйте, например, на 101
ответ 193
число 101 включает 9 однозначных чисел (9 символов), 90 двузначных (180 символов) и 1 трехзначное (3 символа) + 1 = 193
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.07.2013, 18:09     Задача "Натуральный ряд чисел" #18
Цитата Сообщение от Thinker Посмотреть сообщение
101 - ответ 10. задание внимательно прочтите.
так вот в чем дело...
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
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.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.07.2013, 18:33     Задача "Натуральный ряд чисел"
Еще ссылки по теме:

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

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

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

Цитата Сообщение от nonedark2008 Посмотреть сообщение
мне лень
смысл начинать объяснять то, на что банально сил не хватает...
Yandex
Объявления
27.07.2013, 18:33     Задача "Натуральный ряд чисел"
Ответ Создать тему
Опции темы

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