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

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

Войти
Регистрация
Восстановить пароль
 
 
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
#1

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

09.07.2015, 22:17. Просмотров 784. Ответов 30
Метки нет (Все метки)

Дана последовательность из чисел (последовательность из единиц): 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 на их позиции  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2015, 22:17     Проверка делимости 1,11,111,.,11.1 на их позиции
Посмотрите здесь:

C++ Признак делимости и рекурсия
Замена в матрице элементов, меньших 5 на 111 C++
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно. C++
C++ Нахождение критерия делимости
Ввод чисел и проверка их делимости C++
C++ Проверка делимости числа на 11
C++ Однонаправленный список. Операции: удалить элемент из заданной позиции, добавить элемент в заданную позицию,проверка на неравенство
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sn1p3rOk
 Аватар для Sn1p3rOk
281 / 168 / 66
Регистрация: 19.04.2014
Сообщений: 1,079
Завершенные тесты: 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,079
Завершенные тесты: 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,079
Завершенные тесты: 2
09.07.2015, 23:12     Проверка делимости 1,11,111,.,11.1 на их позиции #6
Да ещё 1111%4 = 3. Остаток от деления возвращает 0 или 1 если деление идет на 2. То есть число четное или не четное. Если вы делите на число отличное от двух то остаток от деления будет не только 0 или 1.
ValeryS
Модератор
6449 / 4915 / 451
Регистрация: 14.02.2011
Сообщений: 16,307
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,079
Завершенные тесты: 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,079
Завершенные тесты: 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,079
Завершенные тесты: 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
1252 / 734 / 145
Регистрация: 26.03.2015
Сообщений: 2,763
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,079
Завершенные тесты: 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
1252 / 734 / 145
Регистрация: 26.03.2015
Сообщений: 2,763
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,079
Завершенные тесты: 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++ Графическое изображение делимости
Проверить признак делимости на 11 C++
Заменить все элементы массива, меньшие 5-ти, числом 111 C++
C++ Заменить в массиве все элементы меньшие 5 числом 111

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

Или воспользуйтесь поиском по форуму:
Shamil1
1252 / 734 / 145
Регистрация: 26.03.2015
Сообщений: 2,763
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 на их позиции
Ответ Создать тему
Опции темы

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