Форум программистов, компьютерный форум 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
10.07.2015, 00:12     Проверка делимости 1,11,111,.,11.1 на их позиции #21
Цитата Сообщение от Абубакр Посмотреть сообщение
1111
Это не кратное.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Shamil1
1164 / 646 / 130
Регистрация: 26.03.2015
Сообщений: 2,455
10.07.2015, 00:21     Проверка делимости 1,11,111,.,11.1 на их позиции #22
Цитата Сообщение от Абубакр Посмотреть сообщение
может так?
Нет.
Вы разбейте задачу на простые. И постепенно решайте эти простые задачи.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Main()
{
    const int upto = 100;
    List<uint> devidend = new List<uint>{ 0 };
    uint divider = 0;
    int[] result = new int[upto];
    for(uint i = 0; i < upto; i++)
    {
        MultiplyBy(devidend, 10);
        AddBy(devidend, 1);
        divider = divider + 1;
        uint reminder = Divide(devidend, divider);
        result[i] = reminder == 0 ? 0 : 1;
    }
}
Абубакр
0 / 0 / 0
Регистрация: 08.07.2015
Сообщений: 9
10.07.2015, 00:29  [ТС]     Проверка делимости 1,11,111,.,11.1 на их позиции #23
Цитата Сообщение от Shamil1 Посмотреть сообщение
Поделите число на цифру столбиком на бумаге
На бумаге у меня всё нормально, только на компе не получается

Добавлено через 7 минут
Спасибо ВАМ за советы.
Shamil1
1164 / 646 / 130
Регистрация: 26.03.2015
Сообщений: 2,455
10.07.2015, 00:57     Проверка делимости 1,11,111,.,11.1 на их позиции #24
Вот сложение:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void AddBy(List<uint> a, uint b)
{
    const ulong mask = ((ulong)1 << 32) - 1;
 
    ulong carry = b;
    int i = 0;
    while(carry > 0 && i < a.Count)
    {
        ulong n = carry + a[i];
        a[i++] = (uint)(n & mask);
        carry = n >> 32;
    }
    if(carry > 0)
        a.Add( (uint) carry );
}
Правда, я его не запускал, так что возможна какая-то глупая ошибка.
ulong n - двузначное число (в си это long long unsigned)
mask - 32 единицы - битовая маска младшей цифры в этом числе
a - это массив цифр, начиная с младшего разряда
carry - перенос

126 + 8
carry = 8
6 + 8 = 14, a[0] = 4, carry = 1
2 + 1 = 3, a[1] = 3, carry = 0, выход из цикла

Добавлено через 3 минуты
Умножение почти так же:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MultiplyBy(List<uint> a, uint b)
{
    const ulong mask = ((ulong)1 << 32) - 1;
 
    ulong carry = 0;
    int i = 0;
    while(i < a.Count)
    {
        ulong n = a[i] * b + carry;
        a[i++] = (uint)(n & mask);
        carry = n >> 32;
    }
    if(carry > 0)
        a.Add( (uint) carry );
}
Добавлено через 12 минут
Вот деление, но у меня где-то ошибка, потому-что ответ не сходится:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// не делит, только вычисляет остаток
uint DivideReminder(List<uint> a, uint b)
{
    const ulong mask = ((ulong)1 << 32) - 1;
 
    ulong carry = 0;
    int i = a.Count - 1;
    while(i >= 0)
    {
        ulong n = (carry << 32) + a[i--];
        carry = n % b;
    }
    return (uint)(carry & mask);
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
10.07.2015, 01:10     Проверка делимости 1,11,111,.,11.1 на их позиции #25
на проверяй
до 20 работает точно дальше unsigned long long начинает врать
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
#include <iostream>
 
int mod111(int n)
{
if (n==1) return 0;
int dig=1;
int tmp=n;
while(tmp=tmp/10)
{
    dig++;
}
tmp=n-dig;
int div111=1;
for(int i=0;i<dig;i++)
    div111=div111*10+1;
 div111%=n;
for(int i=0;i<tmp-1;i++)
{
 div111=div111*10+1;
 div111%=n;
}
return div111;
}
 
int main()
{
 int n;
 unsigned long long int a=1;
 std::cin>>n;
    for(int i=0;i<n;i++)
    {
    std:: cout<<i+1<<'\t'<<mod111(i+1)<<'\t'<<(a%(i+1))<<'\t'<<a<<std::endl;
    a=a*10+1;
    }
}
(a%(i+1)) и a=a*10+1; введены для проверки результатов
и на экран выводятся остатки, но легким движением руки, можно поменять на 0 и 1
смысл в делении столбиком но само число я нигде не храню, а генерю на лету
например вводим 4
количество количество цифр в делителе 1(подсчитывает первый цикл)
значит для деления нужно двузначное число 11( генерит 2 цикл)
делим 11 на 4 остаток 3
осталось два разряда число (4хзначное)
умножаем остаток на 10 и прибавляем 1
31 опять делим на 4 остаток 3
остался один разряд
умножаем остаток на 10 и прибавляем 1
31 опять делим на 4 остаток 3
всем этим занимается третий цикл
Shamil1
1164 / 646 / 130
Регистрация: 26.03.2015
Сообщений: 2,455
10.07.2015, 01:37     Проверка делимости 1,11,111,.,11.1 на их позиции #26
Нашёл ошибку:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MultiplyBy(List<uint> a, uint b)
{
    const ulong mask = ((ulong)1 << 32) - 1;
 
    ulong carry = 0;
    int i = 0;
    while(i < a.Count)
    {
        ulong n = (ulong)a[i] * b + carry;
        a[i++] = (uint)(n & mask);
        carry = n >> 32;
    }
    if(carry > 0)
        a.Add( (uint) carry );
}
В строке 9 забыл к ulong привести перед умножением и из-за этого терял первую "цифру" произведения (carry).

Добавлено через 18 минут
Вот полный, отлаженный код.
По сравнению с написанным "вслепую" всего одно изменение - приведение к ulong в функции умножения.
Если закомментировать строку 4 в Main(), то будет выводить остатки.
Можно вместо GetSeq() и IEnumerable обычный цикл использовать: вместо yield return сохранять в массив.
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
void Main()
{
    var res = GetSeq()
        .Select(x => x == 0 ? 0 : 1)
        .Take(50).ToArray();
    Console.WriteLine(string.Join(",", res));
}
 
const ulong mask = ((ulong)1 << 32) - 1;
 
IEnumerable<uint> GetSeq()
{
    List<uint> devidend = new List<uint>{ 0 };
    uint divider = 0;
    
    while(true)
    {
        MultiplyBy(devidend, 10);
        AddBy(devidend, 1);
        divider = divider + 1;
        uint reminder = DivideReminder(devidend, divider);
        yield return reminder;
    }
 
}
 
void AddBy(List<uint> a, uint b)
{
    ulong carry = b;
    int i = 0;
    while(carry > 0 && i < a.Count)
    {
        ulong n = carry + a[i];
        a[i++] = (uint)(n & mask);
        carry = n >> 32;
    }
    if(carry > 0)
        a.Add( (uint) carry );
}
 
void MultiplyBy(List<uint> a, uint b)
{
    ulong carry = 0;
    int i = 0;
    while(i < a.Count)
    {
        ulong n = (ulong)a[i] * b + carry;
        a[i++] = (uint)(n & mask);
        carry = n >> 32;
    }
    if(carry > 0)
        a.Add( (uint) carry );
}
 
// не делит, только вычисляет остаток
uint DivideReminder(List<uint> a, uint b)
{
    ulong carry = 0;
    int i = a.Count - 1;
    while(i >= 0)
    {
        ulong n = (carry << 32) + a[i--];
        carry = n % b;
    }
    return (uint)(carry & mask);
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
10.07.2015, 09:21     Проверка делимости 1,11,111,.,11.1 на их позиции #27
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от ValeryS Посмотреть сообщение
int mod111(int n)
подумал я и решил, что функцию можно упростить
C++
1
2
3
4
5
6
7
8
9
10
11
int mod111_v1(int n)
{
int div111=1;
 div111%=n;
for(int i=0;i<n-1;i++)
{
 div111=div111*10+1;
 div111%=n;
}
 return div111;
}
D_Gon
 Аватар для D_Gon
22 / 11 / 5
Регистрация: 09.07.2015
Сообщений: 47
10.07.2015, 09:30     Проверка делимости 1,11,111,.,11.1 на их позиции #28
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от ValeryS Посмотреть сообщение
подумал я и решил, что функцию можно упростить
похоже я неудачнег ( решил немного перекусить )

Обозначим наши числа как http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{k}.

http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{0} = 1
http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{1} = 11 = 10*{n}_{0} + 1
http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{k+1} = 10*{n}_{k} + 1

Тогда:

http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{k+1}%d = ( 10*{n}_{k} + 1 )%d = ( 10*( {n}_{k}%d ) + 1 )%d

Например:

1%3 = 1;
11%3 = ( 10*( 1%3 ) + 1 )%3 = 11%3 = 2
111%3 = ( 10*( 11%3 ) + 1 )%3 = 0

Так мы избавились от длинной арифметики!
(На самом деле это деление столбиком под другим углом.)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
 
unsigned f( unsigned k ){
 
    unsigned out = 0;
    for ( unsigned u = 0; u < k; ++u )
        out = ( 10*out + 1 )%k;
    return out;
}
 
int main(){
    
    unsigned k;
    std::cin >> k;
 
    for ( unsigned u = 1; u <= k; ++u )
        std::cout << f( u ) << std::endl;
 
    return 0;
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
10.07.2015, 09:51     Проверка делимости 1,11,111,.,11.1 на их позиции #29
D_Gon, несколько формальных придирок
n0не может быть, ибо нет числа с нулем цифр
так что
n1 =1
далее по тексту
второе у тебя в формуле рекурсия, а реализовал через цикл
а так молодец, смог вывести формулу, я к ней подбирался,но выразить не смог
D_Gon
 Аватар для D_Gon
22 / 11 / 5
Регистрация: 09.07.2015
Сообщений: 47
10.07.2015, 09:59     Проверка делимости 1,11,111,.,11.1 на их позиции #30
Цитата Сообщение от ValeryS Посмотреть сообщение
n0не может быть, ибо нет числа с нулем цифр
Это потому что метод работает на все такие задачи с остатком от деления, я сначала рассматривал более общий вариант.
Раньше видел кучу таких задач, где все решали длинной арифметикой. Вот блин осенило, но похоже не только меня, я неудачнег.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2015, 10:07     Проверка делимости 1,11,111,.,11.1 на их позиции
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
10.07.2015, 10:07     Проверка делимости 1,11,111,.,11.1 на их позиции #31
Цитата Сообщение от D_Gon Посмотреть сообщение
но похоже не только меня, я неудачнег.
да ладно
идея то витает в воздухе
Цитата Сообщение от D_Gon Посмотреть сообщение
где все решали длинной арифметикой.
а это чаще всего потому,что не все любят математику
поищи по форуму темы, типа "Нужна ли программисту математика"
и сам увидишь
Yandex
Объявления
10.07.2015, 10:07     Проверка делимости 1,11,111,.,11.1 на их позиции
Ответ Создать тему
Опции темы

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