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

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

Войти
Регистрация
Восстановить пароль
 
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
#1

Числовые последовательности - C++

03.12.2010, 21:43. Просмотров 526. Ответов 7
Метки нет (Все метки)

Господа!Прошу мне помочь, очень долго думал над задачей, и так и не смог сделать:
Есть последовательность чисел a0, a1, a2... an, которая определяется следующим образом: a0=0, а каждое следующие ai(1<=i<=n) вычисляется как наименьшее натуральное число большее чем ai-1, десятичная запись которого не содержит цифр десятичной записи числа ai-1(С++)
Ответте пожалуйста!
Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2010, 21:43     Числовые последовательности
Посмотрите здесь:

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

числовые ряды в С++ - C++
Как записать данный ряд: pi=3+4((1/2*3*4)-(1/4*5*6)+(1/6*7*8)-......) в С++?

Проверка на числовые значения - C++
отладка-командная строка: - как чекнуть и вывести алерт текствой введите корректно значение ПРИ ВВОДЕ некорректного значения -как...

Двумерные числовые массивы - C++
С помощью генератора случайных чисел сформировать квадратную целочисленную матрицу размерности m x m, где значение m &lt;=7 вводится с...

Записать числовые значения из файла в массив - C++
Есть такой код Извините за беспокойство, хотел спросить, как производится запись из файла в массив на языке С++? Есть такой...

Удалить из строки все числовые символы - C++
Здравствуйте, помогите, пожалуйста сделайте задач. Пользователь вводит с клавиатуры строка символов. Удалить из строка все числовые...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
03.12.2010, 23:11     Числовые последовательности #2
Честно говоря, кроме прямого перебора в голову ничего не приходит.
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 <iostream>
#include <iomanip>
#include <time.h>
 
using namespace std;
 
bool has_same_digits(int a, int b)
{
    while (a>0)
    {
        int digit = a%10;
        int z=b;
        a/=10;
        while (z>0)
        {
            if (digit == (z%10))
                return true;
            z/=10;
        }
    }
    return false;
}
 
int main()
{
    srand(static_cast<unsigned int>(time(0)));
 
    int N = 49;
    int last_num = 0;
    for (int i=0; i<N; i++)
    {
        cout << last_num << " ";
        int next_num = last_num +1;
        while (has_same_digits(last_num, next_num)) next_num++;
        last_num = next_num;
    }
 
 
    system("pause");
}
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
04.12.2010, 03:28     Числовые последовательности #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
//////////////////////////////////////////////////////////////////////////////////////
//Есть последовательность чисел a0, a1, a2... an, которая определяется 
//следующим образом: a0=0, а каждое следующие ai(1<=i<=n) вычисляется 
//как наименьшее натуральное число большее чем ai-1, десятичная запись которого 
//не содержит цифр десятичной записи числа ai-1
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <sstream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
typedef long long    T_num;
//////////////////////////////////////////////////////////////////////////////////////
bool  get_next_num(T_num&  num_cur)
{
    std::ostringstream  sout_num_cur;
    sout_num_cur << num_cur;
    T_str  num_cur_str(sout_num_cur.str());    
    
    //Увеличиваем первую цифру num_cur_str по модулю 9, пока она не перестанет
    //совпадать с какой-либо цифрой num_cur.
    char dig_first = num_cur_str[0];
    while(num_cur_str.find(dig_first) != T_str::npos)    
    {
        dig_first = (dig_first - '0') % 9 + 1 + '0';        
    }   
 
    //Находим наименьшую цифру, которой нет в num_cur_str.
    T_str  digits("0123456789");
    T_str::size_type  dig_min_pos = digits.find_first_not_of(num_cur_str);    
    if(dig_min_pos == T_str::npos) return  false;
    char  dig_min = digits[dig_min_pos];
    T_str  num_next_str(num_cur_str.size(), dig_min);
    num_next_str[0] = dig_first;
    if(num_next_str <= num_cur_str)
    {
        num_next_str.push_back(dig_min);
    }
 
    //Создаем входной поток из num_next_str.
    std::istringstream ssin(num_next_str);
    return  ssin >> num_cur;  
}
//////////////////////////////////////////////////////////////////////////////////////
void print_nums()
{
    int    counter  = 0;
    T_num  num_cur  = 0;    
    do
    { 
        ++counter;
        std::cout << num_cur
                  << std::endl;        
    }while(get_next_num(num_cur));
    std::cout << counter
              << " numbers are printed."
              << std::endl;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{       
    print_nums();   
}
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
04.12.2010, 04:48     Числовые последовательности #4
Брутфорс однако... Где-то на 20кк+ начинает серьезно задумываться. После 200кк я уже не ждал.
Оптимизировать не вышло. Вообще полный перебор возможно оптимизировать?
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
#include <iostream>
 
bool nextnumb(int a, int z, int t, int curr)
{
    while(z)
    {
        int tmp=z%10;
        z/=10;
        while(t)
        {
            int tr=t%10;
            t/=10;
            if(tmp == tr)
                return false;
        }
        t=curr;
    }
    return true;
}
 
bool getnumb(int* a, int curr)
{
    int t=curr;
    ++*a;
    int z=*a;
    while(1)
    {
        if(!nextnumb(*a, z, t, curr))
        {
            z=++*a;
        }
        else 
            break;
    }
    return true;
}
 
int main()
{
    int a=0;
    int curr=0;
    std::cout<<a<<'\n';
    while(1)
    {
        if(getnumb(&a, curr))
        {
            std::cout<<a<<'\n';
            curr=a;
        }
        if(!a)
            break;
    }
    return 0;
}
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.12.2010, 08:19     Числовые последовательности #5
Вариант быстрее:
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
#include <iostream>
#include <iomanip>
#include <time.h>
 
using namespace std;
 
int func(int last)
{
    int mas[10]={0}, col=0, temp=0, i, temp1;
    while(last>0)
    {
        if(last>0 && last<10)
            temp1=last;
        mas[last%10]++;
        last/=10;
        col++;
    }
    while(col>0)
    {
        if(temp==0)
        {
            if(temp1==9)
            {
                for(i=1; i<10; i++)
                    if(mas[i]==0)
                    {
                        temp=i;
                        break;
                    }
            }
            else
            {
            for(i=1; i<10; i++)
                if(mas[i]==0 && i>temp1)
                {
                    temp=i;
                    col--;
                    break;
                }
            }
        }
        else
        {
            for(i=0; i<10; i++)
                if(mas[i]==0)
                {
                    while(col>0)
                    {
                        temp*=10; temp+=i; col--;
                    }
                    break;
                }
        }
    }
    return temp;
}
 
int main()
{
        srand(static_cast<unsigned int>(time(0)));
 
        int N = 49;
        int last_num = 1; cout << last_num << " "<<0<<" ";
        for (int i=0; i<N; i++)
        {
                cout << last_num << " ";
                int next_num = func(last_num);
                last_num = next_num;
        }
 
 
        system("pause");
        return 0;
}
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
04.12.2010, 20:09  [ТС]     Числовые последовательности #6
Спасибо
asics
Freelance
Эксперт C++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
04.12.2010, 20:11     Числовые последовательности #7
Цитата Сообщение от shocoladka Посмотреть сообщение
А что такое srand?
Загуглить, религия не позволяет ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2010, 20:55     Числовые последовательности
Еще ссылки по теме:

Числовые массивы заполнить по формуле, с клавиатуры и случайным образом - C++
Числовые массивы. Заполнить по формуле, с клавиатуры, случ. числа. Подскажите пожалуйста как делать такое задание!

Числовые прямые (имеется ли у отрезков общая часть не нулевой длинны?) - C++
Здравствуйте! Помогите пожалуйста решить задачу. Сижу, карпею над учебниками, но боюсь что к завтрашнему мне не осилить. Очень надеюсь на...

Одномерные числовые массивы (найти максимальный элемент, сумму элементов, преобразовать) - C++
В одномерном массиве, состоящем из не более чем n (n&lt;=10) вещественных элементов, вводимых с клавиатуры, вычислить: 1) максимальный по...

Построить элементы в убывающей последовательности и вывести первоначальные индексы последовательности - C++
Здравствуйте, уважаемые форумчане!! Помогите разобраться с лабораторной работой Задача -&gt; Построить элементы в убывающей...


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

Или воспользуйтесь поиском по форуму:
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
04.12.2010, 20:55  [ТС]     Числовые последовательности #8
когда обЪясняют понятнее)

Добавлено через 31 минуту
зачем здесь использовать сранд?
Yandex
Объявления
04.12.2010, 20:55     Числовые последовательности
Ответ Создать тему
Опции темы

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