HELP! 0

Et cetera → Программирование

anonymous написал 2 марта 2004 года в 17:47 (889 просмотров) Ведет себя неопределенно; открыл 1814 темы в форуме, оставил 5575 комментариев на сайте.

Помогите плиз написать прогу на паскале ну или хоть алгоритм?

Задан массив натуральных чисел. Упорядочить элементы массива по возрастанию количества кратных простых делителей. (Кратные простые делители это те которые делятся на 1 и сами на себя).

Ответить Цитировать

Longobard 18:44, 2 марта 2004

Ну и в чем проблема? Я бы поступил так (решение в лоб, думать некогда, возможно можно и порациональнее). Берем дом. массив с эл-ми типа byteи и кол-вом эл-в равном кол-ву чисел в первом массиве. Пусть массив с числами — массив x[1..n] of longint; . И массив y[1..n] of byte.

Берем очередной эл-т из массива x. Считаем ЕГО кол-во простых кратных делителей. Записываем это количество в элемент массива y с таким же номером. Т.е.

for i := 1 to n do
   y[i] := Кол-во_простых_кратных_делителей (x[i]);

Теперь берем и сортируем массив y и ОДНОВРЕМЕННО с ним и массив x. То есть когда переставляем местами эл-ты массива y то переставляем соответствующие эл-ты массива x. Получаем необходимый массив x. Можно также сделать по другому. Можно сделать массив структур, где одно поле-число, а другое — его кол-во кратных простых делителей. Далее упорядочиваем точно так же. Но массив один.

Ну посчитать кол-во простых кратных делителей просто: перебираешь делители (от 1 до num div 2), и проверяешь их на кратность и простоту. Я это делал еще в 9-м классе. Если будет время — напишу тебе эту программулечку. Ну а вообще эта задача элементаран, я не понимаю где тут могут возникнуть проблемы.

Ответить Цитировать

Negative 18:53, 2 марта 2004

LONGOBARD, а не в лом было отвечать?

Ответить Цитировать

anonymous 19:08, 2 марта 2004

Потому и хочется поинтереснее, что задачка тривиальная (раз уж взялись двоечникам домашнее задание делать :-)). Как по поводу следующего алгоритма? Тасуем карты.

1. Находим максимальный элемент массива, М.

2. Извлекаем квадратный корень из M, берем его целую часть и прибавляем 1, получаем К.

3. Для каждого простого числа p меньше или равного K делаем вот что:

Проходим массив задом наперед;

Если текущий элемент массива делится на p, кидаем его в самый конец массива, хвост массива сдвигаем.

4. После того, как все простые числа перебраны, массив упорядочен по числу простых делителей.

Не знаю, будет ли это работать, но выглядит забавно…

Good Luck,

Ответить Цитировать

Longobard 19:28, 2 марта 2004

Ээээ… Можно проверить, а не мог бы ты пояснить по какому алгоритму ты это решал? Просто мне интересно. А чувак щас походу дела офигеет, тут такие разговоры пойдут… Троечную задачку будут решать с помощью какого-нибудь алгоритма из комбинаторики или дискретного анализа :) Он подумает » а может нах его, этот кодинг? Если такие задачи решаются с помощью таких вещей, то что будет дальше». В результате совместных усилий всех кодеров никспа и UT в качестве супермозга будет выработана прога линой не менее 200 строк и использующая алгоритмы [censured] :)

Ответить Цитировать

anonymous 20:48, 2 марта 2004

Резвился это я… Не, не будет работать. Два раза я сглупил, Во-первых, простой делитель не обязян быть меньше чем корень из числа, а во-вторых, у кого самый большой простой делитель, тот и окажется в конце списка. А вовсе не тот, у кого больше простых делителей.

Ну и фиг с ним. :-)

Good Luck,

Ответить Цитировать

decvar 21:10, 2 марта 2004

Сильно…….внушает……

Ответить Цитировать

anonymous 14:53, 3 марта 2004

Вобчем я ее набил но все равно где то ошибка он 0 вместо упорядоченного массива выводит:

Program ind1;

Const N=5;

Var

r,nmax,k,i:byte; c:integer;

b : array [1..N] of integer;

a : array [1..N] of integer;

Function kr (x:integer):integer;

Var i,k,m,l,kv : byte;

a : array [1..100] of integer;

Begin k:=0; kv:=0;

For i:=2 to N div 2 do Begin

m:=N mod i;

If m=0 then begin

k:=k+1;

a[k]:=i; l:=0;

While m=0 do Begin

X:=X div i; m:=X mod i; l:=l+1;

End;End;

if l>1 then kv:=kv+1;

kr:=a[k];

End;

Begin

Writeln;

Write (’Vvedite massiv iz ',n,' elementov: ');

For i:=1 to n do Begin

Read (b);

b:=kr(a);

End;

For k:=n downto 2 do Begin

For i:=2 to k do Begin

if b[nmax]

c:=b[nmax]; b[nmax]:=b[k]; b[k]:=c;

c:=a[nmax]; a[nmax]:=a[k]; a[k]:=c; End;

For i:=1 to i do Write (a[k],' ');

End.

Ответить Цитировать

Longobard 16:36, 3 марта 2004

Ты слышал про написание ЧИТАБЕЛЬНОГО кода? Такие слова как отступы и инетрвалы тебе знакомы? Перепиши по нормальному, тогда и посмотрим.

Ответить Цитировать

Xaos 16:46, 3 марта 2004

Сорри!?

Program ind1;

Const N=5;

Var

r, nmax, k, i : byte;

c : integer;

b : array [1..N] of integer;

a : array [1..N] of integer;

Function kr (x : integer) : integer;

Var i, k, m, l, kv : byte;

a : array [1..100] of integer;

Begin

k:=0; kv:=0;

For i:=2 to N div 2 do Begin

m:=N mod i;

If m=0 then begin

k:=k+1;

a[k]:=i; l:=0;

While m=0 do Begin

X:=X div i;

m:=X mod i;

l:=l+1;

End;

if l>1 then kv:=kv+1;

kr:=a[k];

End;

Begin

Writeln;

Write (’Vvedite massiv iz ',n,' elementov: ');

For i:=1 to n do Begin

Read (b);

b:=kr(a);

End;

For k:=n downto 2 do Begin

For i:=2 to k do Begin

If b[nmax]

end;

c:=b[nmax]; b[nmax]:=b[k]; b[k]:=c;

c:=a[nmax]; a[nmax]:=a[k]; a[k]:=c;

End;

For i:=1 to i do Write (a[k],' ');

End.

Ответить Цитировать

Longobard 19:37, 3 марта 2004

Влом врубацца, но изначально неверно. Ты сначала читвешь массив. Полностью. Затем считаешь простые делители и заполняешь таким раком массив b. А у тебя так:

For i:=1 to n do Begin  
                            Read (b[i]);  
                            b[i]:=kr(a[i]);

не понял! Ты читаешь элемент массива и сразу его портишь. А портить его нельзя, надо посчитать кол-во делитеолей и запихать это в a;. И почему отсчет идет во всех циклах от 2 а не от 1? Короче переписывай по нормальному, а еще лучше посиди и подумай сам. Порисуй на бумажке ход твоего алгоритма, пойми где глюк. Если ты не сможешь решить и такую задачку — то ИМХО бросай ты кодинг. Ничего у тебя путного все равно не выйдет в таком случае.

Ответить Цитировать

anonymous 21:38, 3 марта 2004

И ведь правда ж Паскаль! Умереть и не встать. С надо изучать, а не это несчастье. Ну ладно, что бросается в глаза.

Program ind1;

Const N=5;

Var

r, nmax, k, i : byte;

c : integer;

b : array [1..N] of integer;

a : array [1..N] of integer;

Function kr (x : integer) : integer;

Var i, k, m, l, kv : byte;

a : array [1..100] of integer;

Begin

k:=0; kv:=0;

For i:=2 to N div 2 do Begin

m:=N mod i;

If m=0 then begin // i делит N, OK

//Если N == 5 как у тебя, дальнейшее пропускается

k:=k+1;

a[k]:=i; l:=0;

While m=0 do Begin

X:=X div i;

m:=X mod i;

l:=l+1;

End;

//до этого места

if l>1 then kv:=kv+1; // l не инициализирована, Паскаль, кажется,

// считает ее нулем

kr:=a[k]; // k == 0, a[k] == 0 по той же причине

End;

/* Здесь кончается функция и начинается тело программы, так?*/

Begin

Writeln;

Write (’Vvedite massiv iz ',n,' elementov: ');

For i:=1 to n do Begin

Read (b);

b:=kr(a); //a[] модифицируется в kr

End;

For k:=n downto 2 do Begin

For i:=2 to k do Begin

If b[nmax]

end;

c:=b[nmax]; b[nmax]:=b[k]; b[k]:=c;

c:=a[nmax]; a[nmax]:=a[k]; a[k]:=c;

End;

For i:=1 to i do Write (a[k],' ');

/*************************************************************/

Ладно, слушай. Вот тебе идея, как программу такую писать.

1. Решаем, что делать.

а) Читаем массив nubers[]:

б) Для каждого элемента определяем число его простых делителей

-- это в функцию:

в) Загоняем это число в другой массив primes[];

г) Упорядочиваем numbers[] по primes[] — это процедурой.

д) Выводим numbers[].

Решили. У нас будет:

int NumberOfPrimes(int num);

void OrderArray(int * numberArray, int * primeArray);

int main()

{

const int N; //dimension

int numbers[N], int primes[N];

for(int i=0;i

cin >> numbers; //прочитали

for(int i=0;i

primes = NumberOfPrimes(numbers); //посчитали

OrderArray(numbers, primes); //упорядочили

for(int i=0;i

cout << numbers << » »;

cout << endl;// вывели

return 0;

}

2. Пишем функцию и процедуру. Опять решаем, как мы будем определять количество простых делителей числа x. Если не ударяться в изыски, перебираем все целые меньше x. Если ни на одно из них x не делится, объявляем его простым. Т.е. еще функция

bool isAprime(int x)

{

bool result = true; // презумпция невиновности :-)

for(int i=2;i

if(x % i == 0)

result = false;

return result;

}

Теперь пишем

int NumberOfPrimes(int x)

{

int result = 0;

for(int i=2;i

if(isAprime(i) && x % i == 0) //если i простое и делит x

result++;

return result;

};

Как мы будем упорядочивать массив? Найдем максимальный элемент и запишем его в самый конец. На следующем шаге упорядочим массив на один элемент короче.

void OrderArray(int * numberArray, int * primesArray) //в Паскале это будет

//процедура

{

int currentMax = -1, currentNumber = -1, placeOfMax = -1;

for(j=1;j

{

for(int i=0;i

if(primesArray > currentMax)

{

placeOfMax = i;

currentMax = primesArray;

};

currentNumber = numberArray[placeOfMax]

//Нашли макс. элемент. Переставляем в конец

primesArray[placeOfmax] = primesArray[N-j];

numberArray[placeOfMax] = numberArray[N-j];

primesArray[N-j] = currentMax;

numberArray[N-j] = numberMax;

currentMax = -1;

currentNumber = -1;

placeOfMax = -1;

}; // конец верхнего цикла

};

Усе!! Уфф!!! Сорри, что пишу на C, но что-то ж и тебе надо сделать. Пиши максимально модульно. Разбивай задачу сверху вниз, называй переменные, чтобы было понятно, для чего они используются и пиши больше комментариев. И все будет!

А потом можно еще долго это дело оптимизировать, дебаггить и т.д. :-)

Good Luck,

UT

Ответить Цитировать

anonymous 00:38, 6 марта 2004

По поводу Паскаля. Кто-нибудь знает объективную причину в том, что у нас так популярен Паскаль (ну и Делфи как следствие), кроме как то что на основе его нам преподают программирование? Главное, что хотят нам дать только принципы программирования, а не сам язык (который и создан был для обучения). А в итоге получаем, что люди используют его всегда и везде.

Uncle Theodore
bool isAprime(int x)
{

bool result = true; // презумпция невиновности :-)

for(int i=2;i

if(x % i == 0)

result = false;

return result;

}

Немного неоптимально каждый раз прощитывать является ли число простым или нет — в цикле получать остаток от деления. Я бы сделал прекалькулейт — сформировать массив из простых чисел от 1 до максимального числа из заданного массива. И сделать это без участия операций деления — как на бумажке — путем вычеркивания:

а) 1 — простое число

б) берем след. невычеркнутое число «к» (на первой итерации это «2») и вычеркиваем до конца массива каждое «к»-ое число (для «к»==2 это — 4,6,8..).

Когда очередное «к» — вне границы массива, то все «непростые» числа вычеркнуты

Ответить Цитировать

anonymous 03:23, 6 марта 2004

1 — не простое число :-)

Паскаль, видимо, когда-то был «утвержден» инстанциями как самый наш язык программирования. Ладно, хоть не Бейсик.. :-)

Здесь можно до фига чего оптимизировать. Например, ту же

bool isAprime(in) лучше писать как

bool isAprime(int x)

{

for(int i=2;i

if(x % i == 0)

return true;

return false;

}

Я хотел, в основном дать товарищчу идею, как правильно писать прогу. Там даже несколько ошибок есть. Может, посчитать заранее простые числа и быстрее, хотя — надо знать максимальный элемент массива, и перебирать по массиву тоже не быстро, разве что бинарно. Но тогда код просечь будет трудно, и чел ни фига не поймет за наворотами. :-)

А вообще, не нак уж и плохо он написал. Плохо, что он не умеет искать ошибки, и писать код так, чтобы ошибки легче отлавливались. Но это придет.

Good Luck,

Ответить Цитировать

Genie 12:56, 18 марта 2004

Ага, как зададим, блин, простое число чуть меньше 2^31, так и будет программка считать до посинения число его делителей…

Есть у меня такая. Ищущая все 32-битные простые числа и складывающая их в фалик (числа в десятичной нотации, текстом). Работает ооочень долго (около 8 часов на Cel-1.4 [tualatin]).. Хотя основной цикл — строчек 30 на асме… И не сказать бы, что алгоритм неоптимальный, оптимальнее альтернативного решета Эратосфена ещё ничего не обнаружено.. (точнее можно сделать, но, блин, памяти будет требовать в два раза больше….)

Ответить Цитировать

Последние комментарии

OlegL, 17 декабря в 15:00 → Перекличка 21
REDkiy, 8 июня в 9:09 → Как «замокать» файл для юниттеста в Python? 2
fhunter, 29 ноября 2022 года в 2:09 → Проблема с NO_PUBKEY: как получить GPG-ключ и добавить его в базу apt? 6
Иванн, 9 апреля 2022 года в 8:31 → Ассоциация РАСПО провела первое учредительное собрание 1
Kiri11.ADV1, 7 марта 2021 года в 12:01 → Логи catalina.out в TomCat 9 в формате JSON 1

ecobeing.ru

Экология и вегетарианство на благо всем живым существам Планеты.