Определить сколько простых чисел последовательности в восьмеричном коде не имеют цифры 7

@alexxsuperhero · Регистрация: 11.06.2015

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

Дана последовательность из n целых чисел. Определить сколько простых чисел этой последовательности в восьмеричном коде не имеют цифры 7

Байт · 08.02.2019, 19:32

alexxsuperhero, Что именно не выходит? Перебор числ? Определение простоты? Определение отсутствия цифры 7 ? Восьмеричная система?

~~Verevkin~~ · 08.02.2019, 19:39

Ахтунг! Не отлаживал, писал на ~~струёй~~ мелом заборе.

C++

bool IsPrime(unsigned x)
{
  // в интернетах - на каждом углу :))
}
 
// поиск восьмеричной цифры 7 в числе х
bool hoct7(unsigned x)
{
  while (x)
    if ((x & 7) ^ 7) return true;
    else x >> 3;
    
  return false;
}
 
unsigned wtf(unsigned* x, unsigned count)
{
  unsigned q = 0;
  
  while (count--)
  {
    if (!IsPrime(x[count])) continue;
    if (hoct7(x[count])) continue;
    q++;
  }
  
  return q;
}

@Pavel250 · 08.02.2019, 21:29

Долго вспоминал школьную информатику. Пусть труды не пропадут зря, оставлю этот вариант здесь:

C++

#include <iostream>
#include <math.h>
int count = 0;      //Счетчик
 
int main() {
    int x[] = {1,6,7,16,15,17,18,87,124}; //Ваш массив
    
    //Делим каждое число на 8(до нуля), если в остатке нет 7, то
    //инкрементируем счетчик
    //sizeof(x) / sizeof(*x) - определяет длину массива
    for (int t1 = 0; t1 < sizeof(x) / sizeof(*x); t1++) {
        bool z = false;
        for (int t = 0; x[t1]; t++) {
            if ((x[t1] % 8) == 7) z = true;
            x[t1] /= 8;
        }
        if (!z) count++;
    }
    std::cout << count << std::endl;
    system("pause");
}

@alexxsuperhero · 08.02.2019, 21:41 **[ТС]**

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

int x[] = {1,6,7,16,15,17,18,87,124}; //Ваш массив

А без массива можно как-то обойтись?

@Pavel250 · 08.02.2019, 21:57

Реализация с while приятнее глазу.

C++

#include <iostream>
#include <math.h>
int count = 0;      //Счетчик
 
int main() {
    int x[] = { 1,6,7,16,15,17,18,87,124 }; //Ваш массив
 
    //Делим каждое число на 8(до нуля), если в остатке нет 7, то
    //инкрементируем счетчик
    //sizeof(x) / sizeof(*x) - определяет длину массива
    for (int t = 0; t < sizeof(x) / sizeof(*x); t++) {
        bool z = false;
        while(x[t]){
            if ((x[t] % 8) == 7) z = true;
            x[t] /= 8;
        }
        if (!z) count++;
    }
    std::cout << count << std::endl;
    system("pause");
}

Добавлено через 11 минут

C++

#include <iostream>
#include <math.h>
int count = 0;              //Счетчик
const int xlenth = 10;      //Длинна последовательности
int first = 7;              //первый элемент последовательности
int main() {
    int x[xlenth]; 
    //Инициализируем массив
    for (int tmp = 0; tmp < 10; tmp++, first++) {
        x[tmp] = first;
        bool z = false;
        //Делим каждое число на 8(до нуля), если в остатке нет 7, то
        //инкрементируем счетчик
        //sizeof(x) / sizeof(*x) - определяет длину массива
        while (x[tmp]) {
            if ((x[tmp] % 8) == 7) z = true;
            x[tmp] /= 8;
        }
        if (!z) count++;
    }
    std::cout << count << std::endl;
    system("pause");
}

Байт · 08.02.2019, 22:33

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

Долго вспоминал школьную информатику.

Это хорошее занятие. Полезное. Но в условии надо, чтобы эти числа были еще и простыми. В смысле, не имеющие нетривиальных делителей. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Но ваш код несложно подкорректировать. Просто добавить условие простоты.

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

А без массива можно как-то обойтись?

Можно. Просто вводить числа по одному и проверять. Но надо договориться, что будет окончанием ввода.
Можно и рандомом числа получать. Тут тоже надо договориться кой о чем.
Источник чисел может быть совершенно разным. А проверка - одинакова. Поэтому ее лучше реализовать в виде функции.

@Pavel250 · 08.02.2019, 23:02

Сообщение от Байт

Это хорошее занятие. Полезное. Но в условии надо, чтобы эти числа были еще и простыми.

Точно, спасибо. Проглядел. Вот вариант учитывающий это:

C++

#include <iostream>
#include <math.h>
int count = 0;              //Счетчик
const int xlenth = 10;      //Длинна последовательности
int first = 7;              //первый элемент последовательности
int main() {
    int x[xlenth]; 
    //Инициализируем массив
    for (int tmp = 0; tmp < 10; tmp++, first++) {
        x[tmp] = first;
        bool z = false;
        bool z1 = false;
        //Проверяем простое ли число, если да то z1 ставим в true
        for (int i = 2; i < sqrt(x[tmp]); i++) {
            if (x[tmp] % i == 0) {
                z1 = true;
                break;
            }
        }
        if (!z1) {
            //Делим каждое число на 8(до нуля), если в остатке нет 7, то
            //инкрементируем счетчик
            while (x[tmp]) {
                if ((x[tmp] % 8) == 7) z = true;
                x[tmp] /= 8;
            }
            if (!z) count++;
        }
        
    }
    std::cout << count << std::endl;
    system("pause");
}

Автор темы, протестируйте пожалуйста, уже сил нет на это смотреть

Байт · 08.02.2019, 23:33

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

сил нет на это смотреть

тем не менее, можно пару замечаний?
1. Слишком много "булей". Навярняка можно без них обойтись, не усложняя логику программу. Лучший способ, имхо, обернуть проверки в функцию.
2.

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

for (int i = 2; i < sqrt(x[tmp]); i++) {

Тут одна просто ошибка (число 9 окажется простым) Надо "<="
Вторая - методологическая. Это при каждом проходе цикла будет вычисляться тяжеленькая функция sqrt. И не факт, что компилятор догадается это дело соптимизировать. А даже если и догадается, я бы не стал рассчитывать на его умственные способности. Свои надежнее.
Ну и совсем уж мелкое, чисто вкусовое. Очень я не люблю для решения целочисленных задач привлекать math-функции. Они - приблизительные. У вас есть уверенность, что sqrt(10000) = 100? а не 99.9999 ? Это действительно так (проверялось), но так ли это для всех? Без изучения алгоритма, кода этой функции с уверенностью ответить нельзя. Да и для каждой реализации могут быть расхождения. Вам нужны эти головные боли? Когда можно просто и абсолютно уверено написать

C++

1	for(int i=2; i*i <= x[tmp]; i++)

А топик надоел? - Да ну его! Мои замечания вовсе не к нему относятся, да и решение тут давно уже есть. Просто делюсь крупицами опыта

~~Verevkin~~ · 09.02.2019, 00:35

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

Автор темы, протестируйте пожалуйста, уже сил нет на это смотреть

Я не автор, но мне было скучно.
Поэтому получилось примерно так. Я хз, это автор хотел или чо?

Определить сколько простых чисел последовательности в восьмеричном коде не имеют цифры 7

@Pavel250 · 09.02.2019, 00:50

Байт, Спасибо за советы, учту.
Я хотел сделать меньшее кол-во циклов, поэтому использовал этот вариант(for (int i = 2; i < sqrt(x[tmp]); i++)) и break, чтобы лишние циклы не считать.

Байт · 09.02.2019, 01:00

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

Я хотел сделать меньшее кол-во циклов, поэтому использовал этот вариант(for (int i = 2; i < sqrt(x[tmp]); i++)) и break, чтобы лишние циклы не считать.

Дык, тут-то все правильно. И идея вполне разумна. Но детальки реализации...

@Pavel250 · 09.02.2019, 14:32

Сообщение от Байт

Мои замечания вовсе не к нему относятся, да и решение тут давно уже есть. Просто делюсь крупицами опыта

Спасибо! Советы полезные. Буду еще внимательнее проверять.

Кликните здесь для просмотра всего текста

C++

#include <iostream>
 
int count = 0;              //Счетчик
const int xlength = 10;     //Длинна последовательности
int first = 7;              //первый элемент последовательности
 
bool check_oct7(int x);
bool check_prime_num(int x); 
 
int main() {
    int x[xlength];
    //Инициализируем массив
    for (int tmp = 0; tmp < xlength; tmp++, first++) {
        x[tmp] = first;     
        //Инкрементируем счетчик. если число простое и не содержим
        //в восьмеричном представлении цифру 7
        if (check_prime_num(x[tmp]) && !check_oct7(x[tmp])) count++;
    }
    std::cout << count << std::endl;
    system("pause");
    return 0;
}
//Проверяем простое ли число
bool check_prime_num(int x) {
    for (int i = 2; i*i <= x; i++){
        if (x % i == 0) return false;
    }
    return true;
}
//Проверяем содержит число в восьмеричном
//представлении цифру 7
bool check_oct7(int x) {
    bool tmp = false;
    //Делим каждое число на 8(до нуля), 
    //если в остатке есть 7 возвращаем true
    while (x) {
        if ((x % 8) == 7) tmp=true;
        x /= 8;
    }
    return tmp;
}

Один bool пришлось использовать, так как надо проверить все число целиком.

Байт · 09.02.2019, 14:49

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

Один bool пришлось использовать,

C++

bool check_oct7(int x) {
    while (x) {
        if ((x % 8) == 7) return true;  // А чего его дальше-то проверять? :)
        x /= 8;
    }
    return false;
}

Добавлено через 2 минуты
Так как 8 = 2³

C++

bool check_oct7(int x) {
    while (x) {
        if ((x & 7) == 7) return true;  
        x >>= 3;
    }
    return false;
}

Но эта идея уже была здесь озвучена

@Pavel250 · 09.02.2019, 19:33

Байт, Все не просто, но вроде понял. А как узнать сложность того или иного действия не влезая в сам алгоритм?

Байт · 09.02.2019, 20:13

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

Все не просто, но вроде понял.

Что именно составило трудности и сложности?

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

А как узнать сложность того или иного действия не влезая в сам алгоритм?

Опять же, о чем именно речь? Если о том, чем 2-й код поста 14 отличается от 1-го, то это я пояснить могу. На обычном компе двоичные операции (&, >>) реализуются очень быстро. Двоичное представление и битовые операции это его родная среда. И 1<<3 выполняется несколько быстрее, чем 1*8. Но если вас этот аспект не очень интересует, вполне можете на него положить. И на второй код не обращать внимания. Можете считать это изыском умников.
Более того, алгоритмически оба кода эквивалентны. Второй пользуется некоторыми особенностями ЭВМ, и позволяет сократить время выполнения в пару раз. Но эти разы ни в коем случае не являются показателем качества алгоритма. Они случайны.
А другие мои замечания тоже мало имеют отношения к сложности алгоритма. Скорее, к простоте выражения собственных мыслей.
Удачи вам!

@SomniPhobia · 09.02.2019, 21:13

alexxsuperhero, привет!
Пожалуйста. Держи код.
Получение простых чисел реализовано методом Решета Эратосфена.

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <random>
#include <algorithm>
 
using namespace std;
 
template<typename T>
wostream& operator << (wostream& wos, const vector<T> &v)
{
    for (const auto &value : v)
    {
        wos << value << " ";
    }
    wos << endl;
    return wos;
}
 
vector<int> simple_nums(const size_t &count);
 
int main()
{
    system("color 0A");
    wcout.imbue(locale("rus_rus.866"));
    wcin.imbue(locale("rus_rus.866"));
 
    random_device rd;
    mt19937 g{ rd() };
    uniform_int_distribution<> uid(0, 1000);
    auto gen = [&g, &uid]()
    {
        return uid(g);
    };
    
    wcout << L"Введите кол-во элементов в последовательности ";
    size_t n;
    wcin >> n;
    vector<int> box(n);
    generate_n(box.begin(), n, gen);
    wcout << L"Исходное содержание последовательности" << endl;
    wcout << box << endl;
 
    auto max_ = max_element(box.begin(), box.end());
    auto simples = simple_nums(*max_);
    auto predicate = [&simples](const int &t)
    {
        return find(simples.begin(), simples.end(), t) == simples.end();
    };
    auto it = remove_if(box.begin(), box.end(), predicate);
    box.erase(it, box.end());
    wcout << L"Только простые числа из данной последовательности" << endl;
    wcout << box << endl;
 
    wcout << L"Представление простых чисел последовательсности в восьмерично коде" << endl;
    size_t count = 0u;
    for (const auto &value : box)
    {
        wostringstream woss;
        woss << oct << value;
        wstring num_oct_str = woss.str();
        wcout << value << L" -->oct--> " << num_oct_str << endl;
        bool flag = true;
        for (const auto &digit : num_oct_str)
        {
            if (digit == L'7')
            {
                flag = false;
                break;
            }
        }
        count += !!flag;
    }
    wcout << endl;
    wcout << count << L" чисел этой последовательности являются простыми и в восьмерично записи не имеют цифры 7" << endl << endl;
 
    system("pause");
    return 0;
}
 
vector<int> simple_nums(const size_t &count)
{
    vector<int> simple;
    vector<bool> v(count + 1u, true);
    v[0u] = false;
    v[1u] = false;
    for (size_t p = 2u; p <= count;)
    {
        for (size_t d = p * p; d <= count; d += p)
        {
            v[d] = false;
        }
        auto it = find(v.begin() + p + 1u, v.end(), true);
        p = it - v.begin();
    }
    size_t num = 0u;
    for (const auto &flag : v)
    {
        if (flag)
        {
            simple.push_back(num);
        }
        ++num;
    }
    return simple;
}

@SomniPhobia · 10.02.2019, 08:49

Элементы последовательности с одинаковым значением, подходящих по условиям считать по нескольку раз или каждое число по разу, даже если оно дублируется несколько раз?
Если по разу, то там надо в середине кода set ввести. Например, если 197 в последовательности попалось 3 раза, то к счётчику + 3? Так делает верхний мой код. Если Все 3 вхождения считать за одно (+1 к счётчику), то вот код (он подсчитывает только уникальные выполнения условий).

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <random>
#include <algorithm>
#include <set>
#include <iterator>
 
using namespace std;
 
template<typename T>
wostream& operator << (wostream& wos, const vector<T> &v)
{
    for (const auto &value : v)
    {
        wos << value << " ";
    }
    wos << endl;
    return wos;
}
 
template<typename T>
wostream& operator << (wostream& wos, const set<T> &v)
{
    for (const auto &value : v)
    {
        wos << value << " ";
    }
    wos << endl;
    return wos;
}
 
vector<int> simple_nums(const size_t &count);
 
int main()
{
    system("color 0A");
    wcout.imbue(locale("rus_rus.866"));
    wcin.imbue(locale("rus_rus.866"));
 
    random_device rd;
    mt19937 g{ rd() };
    uniform_int_distribution<> uid(0, 1000);
    auto gen = [&g, &uid]()
    {
        return uid(g);
    };
 
    wcout << L"Введите кол-во элементов в последовательности ";
    size_t n;
    wcin >> n;
    vector<int> box(n);
    generate_n(box.begin(), n, gen);
    wcout << L"Исходное содержание последовательности" << endl;
    wcout << box << endl;
 
    auto max_ = max_element(box.begin(), box.end());
    auto simples = simple_nums(*max_);
    auto predicate = [&simples](const int &t)
    {
        return find(simples.begin(), simples.end(), t) != simples.end();
    };
    set<int> st;
    copy_if(box.begin(), box.end(), inserter(st, st.begin()), predicate);
    wcout << L"Только простые числа из данной последовательности" << endl;
    wcout << st << endl;
 
    wcout << L"Представление простых чисел последовательсности в восьмерично коде" << endl;
    size_t count = 0u;
    for (const auto &value : st)
    {
        wostringstream woss;
        woss << oct << value;
        wstring num_oct_str = woss.str();
        wcout << value << L" -->oct--> " << num_oct_str << endl;
        bool flag = true;
        for (const auto &digit : num_oct_str)
        {
            if (digit == L'7')
            {
                flag = false;
                break;
            }
        }
        count += !!flag;
    }
    wcout << endl;
    wcout << count << L" чисел этой последовательности являются простыми и в восьмерично записи не имеют цифры 7" << endl << endl;
 
    system("pause");
    return 0;
}
 
vector<int> simple_nums(const size_t &count)
{
    vector<int> simple;
    vector<bool> v(count + 1u, true);
    v[0u] = false;
    v[1u] = false;
    for (size_t p = 2u; p <= count;)
    {
        for (size_t d = p * p; d <= count; d += p)
        {
            v[d] = false;
        }
        auto it = find(v.begin() + p + 1u, v.end(), true);
        p = it - v.begin();
    }
    size_t num = 0u;
    for (const auto &flag : v)
    {
        if (flag)
        {
            simple.push_back(num);
        }
        ++num;
    }
    return simple;
}

Добавлено через 11 часов 13 минут

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

count += !!flag;

Это строку можно заменить на

C++

1	count += flag;

С помощью !! я пытался привести тип переменной flag к типу bool, а переменная флаг и так имеет тип bool. В данном контексте можно не ставить !! перед flag.

@SomniPhobia · 10.02.2019, 17:18

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

А как узнать сложность того или иного действия не влезая в сам алгоритм?

Можешь мне скидывать несколько равноправных вариантов кодов, если у меня будет желание, я выполню замер и верну тебе графики, демонстрирующие время работы алгоритмов от определенного параметра.
Для текущей темы по твоим кодам результат таков.
test1 - рыжий (признан самым медленным)
test2 - циан
test3 - зелёный (признан самым быстрым)
test4 - красный
test5 - белый
Всё верно записано из твоих вариантов решений по этой теме?

C++

double test_1(const function<int()> &gen, const size_t &count0)
{
    vector<int> x(count0);
    generate_n(x.begin(), count0, gen);
    auto start = clock_type::now();
    size_t count = 0u;
    //Делим каждое число на 8(до нуля), если в остатке нет 7, то
    //инкрементируем счетчик
    //sizeof(x) / sizeof(*x) - определяет длину массива
    for (int t1 = 0; t1 < count0; t1++)
    {
        bool z = false;
        for (int t = 0; x[t1]; t++)
        {
            if ((x[t1] % 8) == 7) z = true;
            x[t1] /= 8;
        }
        if (!z) count++;
    }
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}
 
double test_2(const function<int()> &gen, const size_t &count0)
{
    vector<int> x(count0);
    generate_n(x.begin(), count0, gen);
    auto start = clock_type::now();
    size_t count = 0u;
    for (int t = 0; t < count0; t++)
    {
        bool z = false;
        while (x[t])
        {
            if ((x[t] % 8) == 7) z = true;
            x[t] /= 8;
        }
        if (!z) count++;
    }
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}
 
double test_3(const function<int()> &gen, const size_t &count0)
{
    vector<int> x(count0);
    generate_n(x.begin(), count0, gen);
    auto start = clock_type::now();
 
    int count = 0;              //Счетчик
    //const int xlenth = count0;      //Длинна последовательности
    int first = 7;              //первый элемент последовательности
 
        //int x[xlenth];
        //Инициализируем массив
        for (int tmp = 0; tmp < 10; tmp++, first++)
        {
            x[tmp] = first;
            bool z = false;
            //Делим каждое число на 8(до нуля), если в остатке нет 7, то
            //инкрементируем счетчик
            //sizeof(x) / sizeof(*x) - определяет длину массива
            while (x[tmp])
            {
                if ((x[tmp] % 8) == 7) z = true;
                x[tmp] /= 8;
            }
            if (!z) count++;
        }
 
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}
 
double test_4(const function<int()> &gen, const size_t &count0)
{
    vector<int> x(count0);
    generate_n(x.begin(), count0, gen);
    auto start = clock_type::now();
 
    int count = 0;              //Счетчик
    //const int xlenth = 10;      //Длинна последовательности
    int first = 7;              //первый элемент последовательности
 
        //int x[xlenth];
        //Инициализируем массив
        for (int tmp = 0; tmp < 10; tmp++, first++)
        {
            x[tmp] = first;
            bool z = false;
            bool z1 = false;
            //Проверяем простое ли число, если да то z1 ставим в true
            for (int i = 2; i < sqrt(x[tmp]); i++)
            {
                if (x[tmp] % i == 0)
                {
                    z1 = true;
                    break;
                }
            }
            if (!z1)
            {
                //Делим каждое число на 8(до нуля), если в остатке нет 7, то
                //инкрементируем счетчик
                while (x[tmp])
                {
                    if ((x[tmp] % 8) == 7) z = true;
                    x[tmp] /= 8;
                }
                if (!z) count++;
            }
 
        }
 
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}
 
double test_5(const function<int()> &gen, const size_t &count0)
{
    vector<int> x(count0);
    generate_n(x.begin(), count0, gen);
    auto start = clock_type::now();
 
    int count = 0;              //Счетчик
    const int xlength = 10;     //Длинна последовательности
    int first = 7;              //первый элемент последовательности
 
    //int x[xlength];
    //Инициализируем массив
    for (int tmp = 0; tmp < xlength; tmp++, first++)
    {
        x[tmp] = first;
        //Инкрементируем счетчик. если число простое и не содержим
        //в восьмеричном представлении цифру 7
        if (check_prime_num(x[tmp]) && !check_oct7(x[tmp])) count++;
    }
 
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}

@SomniPhobia · 10.02.2019, 17:40

Тесты запускал несколько раз. Характер графиков не меняется. Расположение кругляшков одинаково.

@alexxsuperhero 0 / 0 / 0 Регистрация: 11.06.2015 Сообщений: 17
		1
	Определить сколько простых чисел последовательности в восьмеричном коде не имеют цифры 7 08.02.2019, 19:18. Показов 1706. Ответов 24 Метки нет (Все метки) Дана последовательность из n целых чисел. Определить сколько простых чисел этой последовательности в восьмеричном коде не имеют цифры 7 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	08.02.2019, 19:32	2
	alexxsuperhero, Что именно не выходит? Перебор числ? Определение простоты? Определение отсутствия цифры 7 ? Восьмеричная система? 0

@alexxsuperhero 0 / 0 / 0 Регистрация: 11.06.2015 Сообщений: 17
	08.02.2019, 21:41 [ТС]	5
	Сообщение от Pavel250 int x[] = {1,6,7,16,15,17,18,87,124}; //Ваш массив А без массива можно как-то обойтись? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	08.02.2019, 22:33	7
	Сообщение от Pavel250 Долго вспоминал школьную информатику. Это хорошее занятие. Полезное. Но в условии надо, чтобы эти числа были еще и простыми. В смысле, не имеющие нетривиальных делителей. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Но ваш код несложно подкорректировать. Просто добавить условие простоты. Сообщение от alexxsuperhero А без массива можно как-то обойтись? Можно. Просто вводить числа по одному и проверять. Но надо договориться, что будет окончанием ввода. Можно и рандомом числа получать. Тут тоже надо договориться кой о чем. Источник чисел может быть совершенно разным. А проверка - одинакова. Поэтому ее лучше реализовать в виде функции. 0

~~Verevkin~~ Заблокирован
	09.02.2019, 00:35	10
	Сообщение от Pavel250 Автор темы, протестируйте пожалуйста, уже сил нет на это смотреть Я не автор, но мне было скучно. Поэтому получилось примерно так. Я хз, это автор хотел или чо? 1

@Pavel250 51 / 37 / 14 Регистрация: 05.08.2016 Сообщений: 187
	09.02.2019, 00:50	11
	Байт, Спасибо за советы, учту. Я хотел сделать меньшее кол-во циклов, поэтому использовал этот вариант(for (int i = 2; i < sqrt(x[tmp]); i++)) и break, чтобы лишние циклы не считать. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	09.02.2019, 01:00	12
	Сообщение от Pavel250 Я хотел сделать меньшее кол-во циклов, поэтому использовал этот вариант(for (int i = 2; i < sqrt(x[tmp]); i++)) и break, чтобы лишние циклы не считать. Дык, тут-то все правильно. И идея вполне разумна. Но детальки реализации... 0

@Pavel250 51 / 37 / 14 Регистрация: 05.08.2016 Сообщений: 187
	09.02.2019, 19:33	15
	Байт, Все не просто, но вроде понял. А как узнать сложность того или иного действия не влезая в сам алгоритм? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	09.02.2019, 20:13	16
	Сообщение от Pavel250 Все не просто, но вроде понял. Что именно составило трудности и сложности? Сообщение от Pavel250 А как узнать сложность того или иного действия не влезая в сам алгоритм? Опять же, о чем именно речь? Если о том, чем 2-й код поста 14 отличается от 1-го, то это я пояснить могу. На обычном компе двоичные операции (&, >>) реализуются очень быстро. Двоичное представление и битовые операции это его родная среда. И 1<<3 выполняется несколько быстрее, чем 1*8. Но если вас этот аспект не очень интересует, вполне можете на него положить. И на второй код не обращать внимания. Можете считать это изыском умников. Более того, алгоритмически оба кода эквивалентны. Второй пользуется некоторыми особенностями ЭВМ, и позволяет сократить время выполнения в пару раз. Но эти разы ни в коем случае не являются показателем качества алгоритма. Они случайны. А другие мои замечания тоже мало имеют отношения к сложности алгоритма. Скорее, к простоте выражения собственных мыслей. Удачи вам! 1

@SomniPhobia 599 / 436 / 136 Регистрация: 22.11.2017 Сообщений: 1,340
	10.02.2019, 17:40	20
	Тесты запускал несколько раз. Характер графиков не меняется. Расположение кругляшков одинаково. 0