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

@Абубакр · Регистрация: 08.07.2015

Студворк — интернет-сервис помощи студентам

Дана последовательность из чисел (последовательность из единиц): 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 сохраняются только единицы. Помогите решить задачу.
Вот что у меня получается:

@Sn1p3rOk · 10.07.2015, 00:12

Сообщение от Абубакр

1111

Это не кратное.

@Shamil1 · 10.07.2015, 00:21

Сообщение от Абубакр

может так?

Нет.
Вы разбейте задачу на простые. И постепенно решайте эти простые задачи.

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;
    }
}

@Абубакр · 10.07.2015, 00:29 **[ТС]**

Сообщение от Shamil1

Поделите число на цифру столбиком на бумаге

На бумаге у меня всё нормально, только на компе не получается

Добавлено через 7 минут
Спасибо ВАМ за советы.

@Shamil1 · 10.07.2015, 00:57

Вот сложение:

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 · 10.07.2015, 01:10

на проверяй
до 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 · 10.07.2015, 01:37

Нашёл ошибку:

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 · 10.07.2015, 09:21

Сообщение от 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 · 10.07.2015, 09:30

Сообщение от ValeryS

подумал я и решил, что функцию можно упростить

похоже я неудачнег ( решил немного перекусить )

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

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

Тогда:

$https://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 · 10.07.2015, 09:51

D_Gon, несколько формальных придирок

n₀не может быть, ибо нет числа с нулем цифр
так что
n₁ =1
далее по тексту
второе у тебя в формуле рекурсия, а реализовал через цикл
а так молодец, смог вывести формулу, я к ней подбирался,но выразить не смог

@D_Gon · 10.07.2015, 09:59

Сообщение от ValeryS

n0не может быть, ибо нет числа с нулем цифр

Это потому что метод работает на все такие задачи с остатком от деления, я сначала рассматривал более общий вариант.
Раньше видел кучу таких задач, где все решали длинной арифметикой. Вот блин осенило, но похоже не только меня, я неудачнег.

ValeryS · 10.07.2015, 10:07

Сообщение от D_Gon

но похоже не только меня, я неудачнег.

да ладно

идея то витает в воздухе

Сообщение от D_Gon

где все решали длинной арифметикой.

а это чаще всего потому,что не все любят математику
поищи по форуму темы, типа "Нужна ли программисту математика"
и сам увидишь

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

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

Решение

Решение

ValeryS Модератор 8982 / 6749 / 921 Регистрация: 14.02.2011 Сообщений: 23,875
	10.07.2015, 09:51
	D_Gon, несколько формальных придирок n₀не может быть, ибо нет числа с нулем цифр так что n₁ =1 далее по тексту второе у тебя в формуле рекурсия, а реализовал через цикл а так молодец, смог вывести формулу, я к ней подбирался,но выразить не смог 1