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

Проверка делимости 1,11,111,.,11.1 на их позиции - C++

Восстановить пароль Регистрация
 
 
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 22:17     Проверка делимости 1,11,111,.,11.1 на их позиции #1
Дана последовательность из чисел (последовательность из единиц): 1, 11, 111, ..., 11..1. (до N)
Требуется определить делимость числа на его порядковый номер и записать в массив 0 или 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
63
64
65
66
67
68
69
70
#include <iostream>
#include <string>
#include <stdlib.h>
#include <sstream>
 
using namespace std;
 
template <typename T>
string toStr(T val){
    ostringstream oss;
    oss<< val;
    return oss.str();
}
 
int main()
{
//-----------------ВВОД ВЫВОД ПОСЛЕДОВАТЕЛЬНОСТЕЙ------------------
    int i,j,N;
    cout<<"Vvedite N:";
    cin>>N;
    cout<<endl;
 
    string *a=new string[N];
    int *is_div = new int[N];
 
    a[0]="1";
    for(i=1;i<N;++i)
        for(j=0;j<=i;++j)
            a[i]+='1';
    for(i=0;i<N;++i)
        cout<<a[i]<<endl;
//--------АЛГОРИТМ ДЕЛЕНИЯ--------------------------
    string x;
    int dlina_a,x_ch,ost,result_ost;
 
    for(i=0;i<N;++i){
//N_a - Номер числа, kolpos_N - Кол.-во цифр в числе, dlina_a - длина числа
            int N_a=i+1,N1=N_a,kolpos_N=0,dlina_a=N_a;
 
            while(N1>0){
                N1=N1/10;
                kolpos_N++;
            }
        while(dlina_a>0){
            x=a[i].substr(0,kolpos_N);
                dlina_a-=kolpos_N;
                    a[i]=a[i].erase(0,kolpos_N);
            x_ch = atoi(x.c_str());
            if(x_ch<N_a){
                x+=a[i].substr(0,1);
                a[i]=a[i].erase(0,1);
                dlina_a-=1;
            }
            ost = x_ch%N_a;
            if(ost==0 && dlina_a>0)
                continue;
            else if(ost!=0 && dlina_a>0)
                a[i]=toStr(ost)+a[i];
            else
                result_ost=ost;
        }
        if(result_ost)
            is_div[i]=1;
        else
            is_div[i]=0;
    }
    for(int k=0;k<N;++k)
        cout<<is_div[k]<<"\n";
    return 0;
}
В массив is_div должны сохраняться ответы 0-"нет" или 1-"да".
У меня выводит, что 1%1=0, 11%2=1, 111%3=1 - ошибка. т.е. после первого цикла в is_div сохраняются только единицы. Помогите решить задачу.
Вот что у меня получается:
Миниатюры
Проверка делимости 1,11,111,.,11.1 на их позиции  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 22:43     Проверка делимости 1,11,111,.,11.1 на их позиции #2
Для начала 111 % 3 = 0.
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 22:49  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #3
НУ и я об этом, у меня выводит 1-цы
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 22:55     Проверка делимости 1,11,111,.,11.1 на их позиции #4
Поясните мне смысле 26 и 27 строки зачем присваивать значение а[0] = "1" ?
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 23:05  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #5
Чтобы в цикле конкатенировать 1-цы в массив.
a[0]="1"
a[1]="11"
...
a[N-1]="11..1" (кол-во единиц=N)

Проблема в алгоритме, а не вводе выводе
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 23:12     Проверка делимости 1,11,111,.,11.1 на их позиции #6
Да ещё 1111%4 = 3. Остаток от деления возвращает 0 или 1 если деление идет на 2. То есть число четное или не четное. Если вы делите на число отличное от двух то остаток от деления будет не только 0 или 1.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
09.07.2015, 23:15     Проверка делимости 1,11,111,.,11.1 на их позиции #7
а зачем заморачиватся со строками?
C++
1
2
3
4
5
6
7
unsigned long long a=1;
for(int i=0; i<n;i++)
{
arr[i]=(a%(i+1))==0;
a=a*10+1;
 
}
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 23:15     Проверка делимости 1,11,111,.,11.1 на их позиции #8
Цитата Сообщение от Абубакр Посмотреть сообщение
Чтобы в цикле конкатенировать 1-цы в массив.
a[0]="1"
C++
1
2
3
4
5
6
7
8
9
10
11
12
// Зачем так ?
a[0]="1";
    for(i=1;i<N;++i)
        for(j=0;j<=i;++j)
            a[i]+='1';
 
// Если правильнее сделать так
for (i = 0; i < N; i ++)
    for (j = 0; j <= i; j ++)
        a[i] += '1';
 
// И не нужно никакое a[0] = "1";
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 23:17  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #9
is_dev - массив, в котором сохраняются ответы: 0-"число не делится на свой порядковый номер" 1-"делится"
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 23:27     Проверка делимости 1,11,111,.,11.1 на их позиции #10
Вот держи код.
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
#include <iostream>
#include <sstream>
#include <string>
 
using namespace std;
 
int main()
{
    int N = 5;
    
    int is_dev[N];
    
    string* a = new string[N];
    
    for (int i = 0; i < N; i ++)
    {
        for (int j = 0; j <= i; j ++)
        {
            a[i] += '1';
        }
    }
 
    for (int i = 0; i < N; i ++)
    {
        cout << a[i] << endl;
    }
    
    int some_int;
    
    for (int i = 0; i < N; i ++)
    {
        // Вместо atoi
        istringstream buffer(a[i]);
        buffer >> some_int;
 
        if (some_int % (i + 1) > 0)
        {
            is_dev[i] = 1;
        }
        else
        {
            is_dev[i] = 0;
        }
    }
    
    for (int i = 0; i < N; i ++)
    {
        cout << is_dev[i] << endl;
    }
    
    return 0;
}
Добавлено через 2 минуты
Естественно здесь только та часть кода с которой у тебя проблема. Изменишь под свой код и все будет ок.
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 23:30  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #11
Цитата Сообщение от ValeryS Посмотреть сообщение
а зачем заморачиватся со строками?
Если длина числа больше чем long long int
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 23:31     Проверка делимости 1,11,111,.,11.1 на их позиции #12
Работоспособность кода выше можешь проверить по ссылке.
http://ideone.com/fudUK2
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 23:40  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #13
Например, если вводить N=250, то получится 1111111....111111, т.е. огромное число и это его невозможно одним условием проверить. Надо разбивать и проверять по частям, но у меня не получается.

Добавлено через 3 минуты
Sn1p3rOk, спасибо за исходник. Можешь сделать для чисел, длина которых больше 10 цифр?
Shamil1
1167 / 649 / 130
Регистрация: 26.03.2015
Сообщений: 2,458
09.07.2015, 23:41     Проверка делимости 1,11,111,.,11.1 на их позиции #14
Цитата Сообщение от Абубакр Посмотреть сообщение
Если длина числа больше чем long long int
Есть специальные библиотеки. Например, gmp.
Или Вы хотите самостоятельно реализовать деление длинных чисел?

Тогда число надо хранить не в массиве строк, а в массиве unsigned long.
Делить столбиком, считая каждый из элементов массива за одну цифру.
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
09.07.2015, 23:48     Проверка делимости 1,11,111,.,11.1 на их позиции #15
Цитата Сообщение от Абубакр Посмотреть сообщение
Например, если вводить N=250, то получится 1111111....111111, т.е. огромное число
Это уже бред получится, число из 250 знаков превышает количество частиц во Вселенной (видимой).
Я даже понять не смогу кому будет нужно число большее гугола. Прошу не путать с Google
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
09.07.2015, 23:54  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #16
длинные числа называются, чтоб чёрт их побрал
Shamil1
1167 / 649 / 130
Регистрация: 26.03.2015
Сообщений: 2,458
09.07.2015, 23:58     Проверка делимости 1,11,111,.,11.1 на их позиции #17
В Вашем случае деление длинного числа на короткое (цифру), так как вряд ли номер элемента в последовательности выйдет за пределы unsigned long. В процессе деления столбиком Вам нужно будет делить двузначное число (первая цифра которого - это остаток от предыдущего деления) на цифру. Для этой операции используйте unsigned long long.

Добавлено через 2 минуты
Цитата Сообщение от Абубакр Посмотреть сообщение
длинные числа называются, чтоб чёрт их побрал
Простой же алгоритм. Поделите число на цифру столбиком на бумаге, а потом воспроизведите те же действия, но уже с большими цифрами.
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,078
Завершенные тесты: 2
10.07.2015, 00:02     Проверка делимости 1,11,111,.,11.1 на их позиции #18
Абубакр, Боюсь что после 17-ти значного числа остаток от деление на их порядковых номер будет равен 1.

Добавлено через 3 минуты
Но это моё предположение.
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
10.07.2015, 00:07  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #19
Shamil1,

unsigned long long **a=new *long long[N]
for(i=0;i<N;++i)
for(j=0;j<i;++j){
*a=new long long[i];
a[i][j]+='1';
}
может так?

Добавлено через 1 минуту
Sn1p3rOk, нет, существуют - кратные 111, 1111,...)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2015, 00:07     Проверка делимости 1,11,111,.,11.1 на их позиции
Еще ссылки по теме:

C++ признак делимости на три C++
C++ Однонаправленный список. Операции: удалить элемент из заданной позиции, добавить элемент в заданную позицию,проверка на неравенство
Проверка делимости чисел C++

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

Или воспользуйтесь поиском по форуму:
Shamil1
1167 / 649 / 130
Регистрация: 26.03.2015
Сообщений: 2,458
10.07.2015, 00:07     Проверка делимости 1,11,111,.,11.1 на их позиции #20
Цитата Сообщение от Sn1p3rOk Посмотреть сообщение
Боюсь что после 17-ти значного числа остаток от деление на их порядковых номер будет равен 1.
Вот первые сто остатков:
Код
[0,1,0,3,1,3,1,7,0,1,1,3,1,11,6,7,1,9,1,11,6,11,1,15,11,11,0,19,1,21,1,7,12,11,16,27,1,11,33,31,1,21,1,11,36,11,1,39,36,11,9,19,1,27,1,39,54,11,1,51,1,11,27,7,61,33,1,23,42,61,1,63,1,11,36,47,23,39,1,71,0,11,1,63,61,11,24,55,1,81,1,7,18,11,91,39,1,25,45,11]
Yandex
Объявления
10.07.2015, 00:07     Проверка делимости 1,11,111,.,11.1 на их позиции
Ответ Создать тему
Опции темы

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