[COLOR=#000000][COLOR=#0000bb]bool simpleNum[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]int num[/COLOR][COLOR=#007700]) [/COLOR][COLOR=#ff8000]//определяет простое число или нет
[/COLOR][COLOR=#007700]{
bool IsSimple = false;
[/COLOR][COLOR=#0000bb]int counter [/COLOR][COLOR=#007700]= [/COLOR][COLOR=#0000bb]2[/COLOR][COLOR=#007700];
while ([/COLOR][COLOR=#0000bb]counter [/COLOR][COLOR=#007700]< [/COLOR][COLOR=#0000bb]num[/COLOR][COLOR=#007700])
{
if ([/COLOR][COLOR=#0000bb]num[/COLOR][COLOR=#007700]%[/COLOR][COLOR=#0000bb]counter [/COLOR][COLOR=#007700]== [/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700])
{
IsSimple = true;
break;
}[/COLOR][COLOR=#007700]
[/COLOR][COLOR=#0000bb]counter[/COLOR][COLOR=#007700]++;
}
return [/COLOR][/COLOR][COLOR=#000000][COLOR=#007700]IsSimple[/COLOR][/COLOR][COLOR=#000000][COLOR=#007700];
}[/COLOR][/COLOR]
Задача: удалить из массива все простые числа
Задача: удалить из массива все простые числа (естественно числа разумные).
Пример:
исходный массив: 10 20 11 7 9 15
новый массив: 10 20 9 15
Какие идеи, комментарии по коду, спасибо за внимание.
Пример:
исходный массив: 10 20 11 7 9 15
новый массив: 10 20 9 15
Какие идеи, комментарии по коду, спасибо за внимание.
Код:
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
void showArray(int *ar, int l) //вывод массива
{
for(int i=0; i<l; i++) cout<<ar<<" ";
cout<<"\n\n";
}
bool simpleNum(int num) //определяет простое число или нет
{
int counter = 2;
while (counter < num)
{
if (num%counter == 0) return false;
counter++;
}
return true;
}
int* delSimpleNums(int *ar, int &N)
{
int size = N, *temp, k=0;
for(int i=0; i<N; i++)
if(simpleNum(ar)) //ищем простое число
{
ar = -1; //флаг
--size;
}
temp = new int[size]; //выделяем память для нового массива
for(int i=0; i<N; i++)
if(ar!=-1)
{
temp[k]=ar; //перезапись без прост чисел
k++;
}
delete []ar;
N = size;
return temp;
}
void main()
{
int N, *ar;
cout<<"Number of elements of an array:"<<endl;
cin>>N;
ar = new int [N];
for(int i=0; i<N; i++)
{
ar = rand()%100;
cout<<ar<<" ";
}
cout<<"\n\n";
int *br = delSimpleNums(ar, N);
showArray(br,N);
delete []br;
}
#include <stdlib.h>
#include <time.h>
using namespace std;
void showArray(int *ar, int l) //вывод массива
{
for(int i=0; i<l; i++) cout<<ar<<" ";
cout<<"\n\n";
}
bool simpleNum(int num) //определяет простое число или нет
{
int counter = 2;
while (counter < num)
{
if (num%counter == 0) return false;
counter++;
}
return true;
}
int* delSimpleNums(int *ar, int &N)
{
int size = N, *temp, k=0;
for(int i=0; i<N; i++)
if(simpleNum(ar)) //ищем простое число
{
ar = -1; //флаг
--size;
}
temp = new int[size]; //выделяем память для нового массива
for(int i=0; i<N; i++)
if(ar!=-1)
{
temp[k]=ar; //перезапись без прост чисел
k++;
}
delete []ar;
N = size;
return temp;
}
void main()
{
int N, *ar;
cout<<"Number of elements of an array:"<<endl;
cin>>N;
ar = new int [N];
for(int i=0; i<N; i++)
{
ar = rand()%100;
cout<<ar<<" ";
}
cout<<"\n\n";
int *br = delSimpleNums(ar, N);
showArray(br,N);
delete []br;
}
Цитата: Stalcer
Задача: удалить из массива все простые числа (естественно числа разумные).
А отзывы будут такие. Всё нижеперечисленное есть не более чем IMHO и не претендует на звание единственно верного.
1. Для каждого элемента массива вызывается функция simpleNum(), где в цикле вычисляется остаток от деления. Хорошо, если у нас в масиве числа не больше 100. А если не больше 1000000 и 100000 элементов масива? Лучше заранее найти простые числа методом решета Эратосфена и где-нибудь их прикопать. Памяти при этом, понятно, больше расходуется, но работать должно намного быстрее.
2. Если уж мы пишем на C++, можно использовать шаблон vector, он хоть и работает медленнее, чем просто обращение к массиву, зато позволяет удалять отдельные элементы и менять длину по ходу пьесы. Заодно избавимся от необходимости вызывать delete[]. Последнее обстоятельство важно в "больших" программах, когда есть вероятность, что где-то между new[] и delete[] может возникнуть исключение, и наш delete[] не успеет отработать (впрочем, можно выкрутиться, используя try{} __finally{}).
3. Не пишите void main(), ибо тогда с большой долей вероятности программа будет де-юре завершаться аварийно (т.е. возвращать ненулевой errorlevel). Почему -- читайте документацию. Пишите int main() { ... return 0; }
4. По возможности, вызывайте delete[] в том же блоке, что и new[]. Иначе в "больших" программах долго будете утечки памяти искать.
5. Н. Вирт говорил, что в процедуре должен быть один вход и один выход. Я к тому, что если уж искать простые числа в цикле, то, согласно принципам структурного программирования, это лучше делать примерно так:
Код:
Задача вдохновила меня накропать следующее.
Код:
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
using namespace std;
#define MaxVal 100
typedef vector <int> VectorOfInt;
void FillVector(VectorOfInt &v); // заполнить массив случайными числами
void PrintVector(VectorOfInt &v); // вывести массив на экран
void FillGrid(VectorOfInt &g); // заполнить решето Эратосфена
void DropPrime(VectorOfInt &v, VectorOfInt &g); // удалить простые числа
int _tmain(int argc, _TCHAR* argv[])
{
VectorOfInt ar;
VectorOfInt EraGrid(MaxVal); // для решета Эратосфена
FillVector(ar);
PrintVector(ar);
FillGrid(EraGrid);
DropPrime(ar, EraGrid);
cout << endl << "Now without prime numbers:" << endl;
PrintVector(ar);
return 0;
}
void FillVector(VectorOfInt &v)
{
int N;
cout << "Number of elements of an array:";
cin >> N;
v.resize(N);
srand((unsigned)time(NULL));
for(int i = 0; i < N; i++)
v = rand()%MaxVal;
}
void PrintVector(VectorOfInt &v)
{
int N = v.size();
cout << endl << "Vector[" << N << "] =" << endl;
for(int i = 0; i < N; i++)
cout << " ar[" << i << "] = " << v;
cout << endl << endl;
}
void FillGrid(VectorOfInt &v)
{
int N = v.size();
for(int j = 0; j < N; j++)
v[j] = j;
//поскольку 1 не простое число, обнулим ячейку с этим числом
v[1]=0;
for(int k = 2; k < N; k++)
if(v[k])
for(int j = k * 2; j < N; j += k)
v[j]=0; // обнуляем все ячейки, кратные k
// (они по-любому не простые)
}
void DropPrime(VectorOfInt &v, VectorOfInt &g)
{
int N = v.size();
for(int j = N - 1; j >= 0; --j)
if(g[v[j]])
v.erase(v.begin() + j);
// давим элементы массива v, для которых
// есть соответствующие ненулевые элементы
// массива g
// метод erase() принимает в качестве аргумента
// только итераторы (по крайней мере, в Visual C++)
}
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
using namespace std;
#define MaxVal 100
typedef vector <int> VectorOfInt;
void FillVector(VectorOfInt &v); // заполнить массив случайными числами
void PrintVector(VectorOfInt &v); // вывести массив на экран
void FillGrid(VectorOfInt &g); // заполнить решето Эратосфена
void DropPrime(VectorOfInt &v, VectorOfInt &g); // удалить простые числа
int _tmain(int argc, _TCHAR* argv[])
{
VectorOfInt ar;
VectorOfInt EraGrid(MaxVal); // для решета Эратосфена
FillVector(ar);
PrintVector(ar);
FillGrid(EraGrid);
DropPrime(ar, EraGrid);
cout << endl << "Now without prime numbers:" << endl;
PrintVector(ar);
return 0;
}
void FillVector(VectorOfInt &v)
{
int N;
cout << "Number of elements of an array:";
cin >> N;
v.resize(N);
srand((unsigned)time(NULL));
for(int i = 0; i < N; i++)
v = rand()%MaxVal;
}
void PrintVector(VectorOfInt &v)
{
int N = v.size();
cout << endl << "Vector[" << N << "] =" << endl;
for(int i = 0; i < N; i++)
cout << " ar[" << i << "] = " << v;
cout << endl << endl;
}
void FillGrid(VectorOfInt &v)
{
int N = v.size();
for(int j = 0; j < N; j++)
v[j] = j;
//поскольку 1 не простое число, обнулим ячейку с этим числом
v[1]=0;
for(int k = 2; k < N; k++)
if(v[k])
for(int j = k * 2; j < N; j += k)
v[j]=0; // обнуляем все ячейки, кратные k
// (они по-любому не простые)
}
void DropPrime(VectorOfInt &v, VectorOfInt &g)
{
int N = v.size();
for(int j = N - 1; j >= 0; --j)
if(g[v[j]])
v.erase(v.begin() + j);
// давим элементы массива v, для которых
// есть соответствующие ненулевые элементы
// массива g
// метод erase() принимает в качестве аргумента
// только итераторы (по крайней мере, в Visual C++)
}
Цитата: Plisteron
1. Для каждого элемента массива вызывается функция simpleNum(), где в цикле вычисляется остаток от деления. Хорошо, если у нас в масиве числа не больше 100. А если не больше 1000000 и 100000 элементов масива? Лучше заранее найти простые числа методом решета Эратосфена и где-нибудь их прикопать. Памяти при этом, понятно, больше расходуется, но работать должно намного быстрее.
IMHO лучше использовать тесты простоты, чем генераторы.
А используемый автором алгоритм можно ускорить, если делить не на все числа, а на (уже найденные) простые. Т.е. методом динамического программирования.
Цитата: Plisteron
2. Если уж мы пишем на C++, можно использовать шаблон vector, он хоть и работает медленнее, чем просто обращение к массиву, зато позволяет удалять отдельные элементы и менять длину по ходу пьесы.
Да не работает он медленнее, уже столько раз обсуждалось. :)
Но для этой задачи лучше не вектор, а список, т.к. количество вставок-удалений соизмеримо с кол-вом элементов.
Цитата: Plisteron
Задача вдохновила меня накропать следующее.
Ну а если так:
Код:
template<class T, class U>
void DropPrime(const T& src, U& dst)
{
for(typename T::const_iterator it = src.begin(); it != src.end(); ++it)
{
if( !isPrimeNum(*it) ) {
dst.push_back(*it);
}
}
}
void DropPrime(const T& src, U& dst)
{
for(typename T::const_iterator it = src.begin(); it != src.end(); ++it)
{
if( !isPrimeNum(*it) ) {
dst.push_back(*it);
}
}
}
В качестве входных параметров могут быть любые контейнеры, но в качестве выходного (dst) рекомендую list.
Если не хотим другой контейнер, то можно так:
Код:
template<class T>
void DropPrime(const T& src)
{
std::remove_if(src.begin(), src.end(), isPrimeNum);
}
void DropPrime(const T& src)
{
std::remove_if(src.begin(), src.end(), isPrimeNum);
}
Опять же, рекомендую list, queue или т.п.
Plisteron
Если уж мы пишем на C++, можно использовать шаблон vector, он хоть и работает медленнее, чем просто обращение к массиву, зато позволяет удалять отдельные элементы и менять длину по ходу пьесы.
Это из разряда бабушкиных страшилок на ночь.
Если уж мы пишем на C++, можно использовать шаблон vector, он хоть и работает медленнее, чем просто обращение к массиву, зато позволяет удалять отдельные элементы и менять длину по ходу пьесы.
Это из разряда бабушкиных страшилок на ночь.
Цитата: Green
IMHO лучше использовать тесты простоты, чем генераторы.
Чем?
Цитата: Green
А используемый автором алгоритм можно ускорить, если делить не на все числа, а на (уже найденные) простые. Т.е. методом динамического программирования.
Тогда уж лучше искать в уже запомненных числах, а считать новые только в том случае, если тестируемое число больше максимального простого, вычисленного на данный момент. Т.е. получится частный случай моего варианта.
Цитата: Green
Да не работает он медленнее, уже столько раз обсуждалось. :)
Если так, то тем более. Не ошибался только Ленин.
Цитата: Green
Если не хотим другой контейнер, то можно так:
Код:
template<class T>
void DropPrime(const T& src)
{
std::remove_if(src.begin(), src.end(), isPrimeNum);
}
void DropPrime(const T& src)
{
std::remove_if(src.begin(), src.end(), isPrimeNum);
}
Это пойдёт. :)
Цитата: Rififi
Plisteron
Если уж мы пишем на C++, можно использовать шаблон vector, он хоть и работает медленнее, чем просто обращение к массиву, зато позволяет удалять отдельные элементы и менять длину по ходу пьесы.
Это из разряда бабушкиных страшилок на ночь.
Если уж мы пишем на C++, можно использовать шаблон vector, он хоть и работает медленнее, чем просто обращение к массиву, зато позволяет удалять отдельные элементы и менять длину по ходу пьесы.
Это из разряда бабушкиных страшилок на ночь.
Что именно? Что пишем на C++, шаблон vector, что он медленнее или что он позволяет удалять элементы и менять длину?
PS. Ваше сообщение очень помогло Stalcer в решении его задачи.
о, у меня аналогичная задача =) Пасиб
Plisteron, спасибо за советы, действительно дельные. Про решето Эратосфена не слышал, алгоритм крутой, все просто и понятно