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

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

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

Дана последовательность из чисел (последовательность из единиц): 1, 11, 111, ..., 11..1. (до N)
Требуется определить делимость числа на его порядковый номер и записать в массив 0 или 1.
Я написал решение, но с проблемами.
Вот мой код:

C++

#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#

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#

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#

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#

// не делит, только вычисляет остаток
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++

#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#

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#

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++

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++

#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

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

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

@Абубакр 0 / 0 / 0 Регистрация: 08.07.2015 Сообщений: 9
	10.07.2015, 00:29 [ТС]	23
	Сообщение от Shamil1 Поделите число на цифру столбиком на бумаге На бумаге у меня всё нормально, только на компе не получается Добавлено через 7 минут Спасибо ВАМ за советы. 0

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

Решение

Решение

@Sn1p3rOk 287 / 174 / 86 Регистрация: 19.04.2014 Сообщений: 1,095
	10.07.2015, 00:12	21
	Сообщение от Абубакр 1111 Это не кратное. 0

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

@D_Gon 26 / 15 / 17 Регистрация: 09.07.2015 Сообщений: 47
	10.07.2015, 09:59	30
	Сообщение от ValeryS n0не может быть, ибо нет числа с нулем цифр Это потому что метод работает на все такие задачи с остатком от деления, я сначала рассматривал более общий вариант. Раньше видел кучу таких задач, где все решали длинной арифметикой. Вот блин осенило, но похоже не только меня, я неудачнег. 0

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,512
	10.07.2015, 10:07	31
	Сообщение от D_Gon но похоже не только меня, я неудачнег. да ладно идея то витает в воздухе Сообщение от D_Gon где все решали длинной арифметикой. а это чаще всего потому,что не все любят математику поищи по форуму темы, типа "Нужна ли программисту математика" и сам увидишь 0