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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
#1

токены - C++

08.09.2011, 13:58. Просмотров 1690. Ответов 16
Метки нет (Все метки)

здравствуйте! нужны идеи по решению этой задачи. у меня никаких кроме как поделить их на токены...

Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать программу, находящую количество k-чисел, не превосходящих заданное число n.
Формат входных данных:
На первой строке стандартного потока ввода задано число k, на второй — число n (2 <= k <= 100, 1 <= n <= 10100).
Формат выходных данных:
Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, не превышающих n.

Вход: 2 3140
Выход: 31
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2011, 13:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос токены (C++):

Разбиение строки на токены: strtok - C++
нужно чтобы программа разбивала строку с выражением, использую strtok например &quot;6+8+99-76-34&quot; выводила 6 8 99 76 34 + + - ...

Строки, чтение файла, токены - C++
Приложение должно выводить на экран все строки из файла, содержащие двузначные числа. Выводиться только первая строка. Помогите...

Как редактировать токены функции strtok? - C++
Всем доброго времени суток! Есть задание, надо в символьной строке найти слова парной длины, добавить к ним с двух сторон символ '%' и...

Разбить СString на токены - Visual C++
Здравствуйте! Не могу разбить СString строку на токены. СString id1; char *token; char *str; str=id1.GetBuffer(); ...

Разбить строку на токены - CMD/BAT
добрый день. есть рабочий батник. он делает как раз то, что нужно. но хотелось бы немножко большего. суть:

Разделение большого текста из файла на токены - Python
Всем привет! Читаю питоном текстовый документ и нигде не могу найти, как его разделить на токены. #!/bin/usr/python3 import re ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.09.2011, 14:04 #2
Просто перебрать все числа до n, если длина числа не кратна k, то сразу отметать, иначе сравнивать все подстроки. Хотя можно и динамику найти, но с такими ограничениями и перебор сойдет.
2
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
08.09.2011, 15:43 #3
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
/////////////////////////////////////////////////////////////////////////////////////////
// Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают 
// интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. 
// Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, 
// число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 
// является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). 
// Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать 
// программу, находящую количество k-чисел, не превосходящих заданное число n.
//
// Формат входных данных:
// На первой строке стандартного потока ввода задано число k, 
// на второй — число n (2 <= k <= 100, 1 <= n <= 10100).
//
// Формат выходных данных:
// Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, 
// не превышающих n.
//
// Вход: 2 3140
// Выход: 31 
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  count_k_numbers_not_great_n
    (
        int  k,
        int  n
    )
{
    int  res = 0;
    for(int  factor_degree = 10; ; factor_degree *= 10)
    {
        int  factor = 1;
        for(int  i = 0; i < k - 1; ++i)
        {
            factor *= factor_degree;
            factor += 1;
        }
        int  mult_min       = factor_degree / 10;
        int  mult_max_real  = n / factor;
        if(mult_max_real < mult_min)  return res;
        res += std::min(mult_max_real, factor_degree - 1) - mult_min + 1;   
    }    
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "k = ";
    int  k = 0;
    std::cin >> k;
 
    std::cout << "n = ";
    int  n = 0;
    std::cin >> n;
    std::cout << "Количество "
              << k
              << "-чисел, не превосходящих "
              << n
              << ", равно "
              << count_k_numbers_not_great_n(k, n)
              << "."
              << std::endl;
}
2
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
08.09.2011, 15:54  [ТС] #4
Цитата Сообщение от diagon Посмотреть сообщение
если длина числа не кратна k
а как узнать та длину перебираемого числа?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.09.2011, 15:58 #5
Цитата Сообщение от jambas92 Посмотреть сообщение
а как узнать та длину перебираемого числа?
C++
1
2
3
#include <cmath>
//...
log10(n) + 1
Только для натуральных чисел.
2
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
08.09.2011, 22:24  [ТС] #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
30
31
32
33
34
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    int k, n;
    int dlina;
    int yaya1, yaya2;
    unsigned long long int x = 1;
    int count = 0;
 
    cin >> k >> n;
 
    for (double i=10; i<=n; i++)
    {
        dlina = log10(i) + 1;
        if (dlina % k == 0)
        {
            for (int j=0; j<dlina-1; j++)
            {
                x = 10 * x;
            }
            yaya1 = i / x;
            yaya2 = (int)i % x;
            if (yaya1==yaya2)
            {
                count++;
            }
            x=1;
        }
    }
    cout << count;
}
0
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
09.09.2011, 13:34 #7

Не по теме:

Большие числа - это сколько десятичных разрядов? double не может гарантировать сохранность более 16 разрядов: подробнее о double.

Добавлено через 14 минут
Прочитав внимательнее заметил, что это к делу не должно относиться. Сорри.



Добавлено через 11 минут
хм... условие смущает. Если у n максимум 10100, то k ведь никак больше 4 в принципе быть не может?
Не прав в том, что при k=3 нужно сверять 3 значения, при k=4 - уже 4. Лучше написать отдельно процедурку разбиения числа на части в массив, переданный по ссылке.
0
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
09.09.2011, 14:38 #8
Цитата Сообщение от jambas92 Посмотреть сообщение
Вход: 2 3140
Выход: 31
почему 31?

3131 3030
2929 2828 2727 2626 2525 2424 2323 2222 2121 2020
1919 1818 1717 1616 1515 1414 1313 1212 1111 1010

итого 22.

909 на сколько понимаю уже не подходит.

или как-то не так?
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
09.09.2011, 15:07 #9
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
72
73
74
75
/////////////////////////////////////////////////////////////////////////////////////////
// Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают 
// интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. 
// Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, 
// число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 
// является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). 
// Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать 
// программу, находящую количество k-чисел, не превосходящих заданное число n.
//
// Формат входных данных:
// На первой строке стандартного потока ввода задано число k, 
// на второй — число n (2 <= k <= 100, 1 <= n <= 10100).
//
// Формат выходных данных:
// Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, 
// не превышающих n.
//
// Вход: 2 3140
// Выход: 31 
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  count_k_numbers_not_great_n
    (
        int  k,
        int  n
    )
{
    int  res = 0;
    for(int  factor_degree = 10; ; factor_degree *= 10)
    {
        int  factor = 1;
        for(int  i = 0; i < k - 1; ++i)
        {
            factor *= factor_degree;
            factor += 1;
        }
        int  mult_min       = factor_degree / 10;
        int  mult_max_real  = n / factor;
        if(mult_max_real < mult_min)  return res;
        int  mult_max = std::min(mult_max_real, factor_degree - 1);
        for(int  mult = mult_min; mult <= mult_max; ++mult)
        {
            std::cout << ++res
                      << ":"
                      << '\t'
                      << mult * factor
                      << std::endl;
        }        
    }    
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "k = ";
    int  k = 0;
    std::cin >> k;
 
    std::cout << "n = ";
    int  n = 0;
    std::cin >> n;
    std::cout << std::endl;
    std::cout << std::endl
              << "Количество "
              << k
              << "-чисел, не превосходящих "
              << n
              << ", равно "
              << count_k_numbers_not_great_n(k, n)
              << "."
              << std::endl;
}
0
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.09.2011, 15:22  [ТС] #10
villu, есть же ведь еще такие варианты:
11, 22, 33, 44, 55, 66, 77, 88, 99,
0
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
09.09.2011, 15:25 #11
а. Задачу не так понял.
0
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.09.2011, 15:37  [ТС] #12
Mr.X, первое решение абсолютно верно, но тест не проходит из за того что n может доходить до 1 <= n <= 10^100).
0
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
09.09.2011, 15:48 #13
Теперь понятно. Коммент о дабл всё же имеет некоторую ценность.
Для таких n про перебор можно забыть, используй логику.
Интересно при k=2 и n=10^100 выходит. Для подсчёта нужно работать с очень большими числами => реализовывать такие числа будет проще в виде строки (нужна лишь операция сложения).

n считывай тоже как строку, кстати.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.09.2011, 16:48 #14
А задачка-то на динамику...
Можно ссылку?
0
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.09.2011, 16:53  [ТС] #15
давай))
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.09.2011, 16:53
Привет! Вот еще темы с ответами:

Как распарсить строку на токены используя регулярные выражения - Java SE
Здравствуйте!Надо распарсить строку такую например &quot;set int MyVar=7&quot; чтобы получились лексемы(токены) token=set и соответственно...

Разбить математическое выражение на токены и занести их в массив строк - C#
Dopustim dana eto: 3+4/6*5-2 Kak mne polucit iz etova massiv string {3,+,4,/,6,*,5,-,2} i nayti kolicestvo operacii? int i = 0; ...


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

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

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