PDA

Просмотр полной версии : Гауссовы целые числа



Bod_r
14.03.2010, 00:50
Помогите пожалуйста написать вот такую штуку :confused:. Заранее благодарен :)


Дано целое Гаусово число n + mi (принадлежащее Z [i]).
Требуется:
- Проверить является ли оно простым (в Z [i]).
- Вывести его разложение на простые (в Z [i]) множители.

Romeo
14.03.2010, 01:14
Это заказ программы за деньги или нужна помощь? Если заказ, то я перемещу в другой раздел. Если просто нужна помощь, то задавай более конкретные вопросы. Что именно не понятно или не знаешь как сделать?

Bod_r
14.03.2010, 01:25
незнаю как сделать :(

Romeo
14.03.2010, 14:03
Ну раз уж ты поленился предоставить теорию для тех, кто не понимает (или забыл) что такое комплексное число или гауссово число (две буквы "с" обязательны), то теорию предоставлю я (ссылка на Википедию (http://ru.wikipedia.org/wiki/%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%BE%D0%B2%D1%8B_% D1%86%D0%B5%D0%BB%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D 0%BB%D0%B0)).

И так, по критерию Гаусса, Гауссово число a + bi является простым тогда и только тогда, когда:
* либо одно из чисел a, b нулевое, а другое — целое простое число вида +-(4n+3);
* либо a, b оба не нули и норма a*a + b*b — простое натуральное число.

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

Далее по поводу второго пункта. Очевидно, что его следует выполнять только в том случае, если гауссово число не являеся простым. Поиск делителей будет несколько усложнён тем фактом, что число комплексное, однако усложнение выразится только в сложности алгоритма, так как однократный поиск делителя мы будем делать двумя вложенными циклами вместо одно цикла в случае натуральных чисел.

Поиск делителя, как и в случае натуральных чисел, сводится к проверке кандидата на делимость. Гауссово число по определению имеет целые Re и Im, а также известно, что кандидат по норме не может быть больше, чем исходное число по норме. Исходя из всего этого, перебор кандидатов не представляет никакой сложности - простой цикл в цикле (один по вещественной, другой по мнимой части числа).

Пробуй реализовать и задавай вопросы, если что-то не будет получаться. Будем помогать. Если передумал писать сам, то дай знать и я перенесу в раздел заказов.

Bod_r
14.03.2010, 14:45
о) спасибо за информацию!
буду пробовать

Taras
17.03.2010, 15:07
У меня такая же задача, она из задачника А. Шенна. Первую часть задания реализовал...а вот алгоритм разложения на простые числа не могу найти:(. Помогите плиззз.

Bod_r
18.03.2010, 00:25
У меня такая же задача, она из задачника А. Шенна. Первую часть задания реализовал...а вот алгоритм разложения на простые числа не могу найти:(. Помогите плиззз.

как ты первую часть зделал???

rrrFer
18.03.2010, 11:58
#include<iostream>
using std::cin;
using std::cout;
using std::endl;
bool checkEasy(int a){
int i,n;
for(i=2,n=a/2+1;i<n;i++)
if(!(a%i))
return 0;
return 1;
}
bool checkEasy(int a, int b){
if(!(a*b))
return !((a+b-3)%4);
return checkEasy(a*a+b*b);
}
int main(){
int a,b;
cin>>a>>b;
cout<<checkEasy(a,b);
cout<<endl<<"press any key to continue: "<<endl;
cin.get(),cin.get();
return 0;
}
первая часть

Bod_r
19.03.2010, 01:31
алгоритм продолжения я уже дописал ... позже выложу

Bod_r
21.03.2010, 02:18
Первую часть переделал, поскольку, она работала не со всеми числами. Дописал вторую часть. Если число Гаусса простое, то происходит розложение на простые множители. Вроде работает так как надо. =)


#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
bool checkEasy(int a, int b)
{

if(a==0)
{
for(int i=2;i<b;i++)
{
if(b%i==0)
{
return 0;
}
}
return 1;
}
if(b==0)
{
for(int i=2;i<a;i++)
{
if(a%i==0)
{
return 0;
}
}
return 1;
}
for(int i=2;i<(a*a+b*b);i++)
{
if((a*a+b*b)%i==0)
{
return 0;
}
}
return 1;

}
void R(int a, int b)
{
for (int i=2;i<=a;i++)
{
for (int j=2;j<a;j++)
{

if (a%i==0 && a%j!=0)
{
a=a/i;
cout <<i<<endl;
}
}
}
for (int i=2;i<=b;i++)
{
for (int j=2;j<b;j++)
{

if (b%i==0 && b%j!=0)
{
b=b/i;
cout <<i<<endl;
}
}
}
}

int main(){
int a,b;
cin>>a>>b;
bool c = checkEasy(a,b);
cout<< c;
cin.get(),cin.get();
if(c==1)
{
cout<<"Easy"<<endl;
R(a,b);
}
else
{
cout<<"not easy";
}




getch();
return 0;
}

rrrFer
21.03.2010, 07:37
Что неправильно работало?
Вижу что сейчас у вас проверка на простоту свялась к проверке действительной и мнимой частей на простоту и проверке на простоту их нормы,но если верить википедии то алгоритм там должен быть другой. ССлылку на википедиювам дали выше. По тем правилам что сказаны в википедии можно сделать вывод что если обе части числа нули - то число непростое,а аткже что число 0+15i или 15+0i является простым.

Bod_r
22.03.2010, 19:09
Что неправильно работало?
Вижу что сейчас у вас проверка на простоту свялась к проверке действительной и мнимой частей на простоту и проверке на простоту их нормы,но если верить википедии то алгоритм там должен быть другой. ССлылку на википедиювам дали выше. По тем правилам что сказаны в википедии можно сделать вывод что если обе части числа нули - то число непростое,а аткже что число 0+15i или 15+0i является простым.

ой. об этой особенности я просто забыл.
извиняюсь. =)