Гауссовы целые числа

Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain

Bod_r
Сообщения: 8
Зарегистрирован: 14 мар 2010, 00:37

Гауссовы целые числа

Сообщение Bod_r » 14 мар 2010, 00:50

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


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

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Гауссовы целые числа

Сообщение Romeo » 14 мар 2010, 01:14

Это заказ программы за деньги или нужна помощь? Если заказ, то я перемещу в другой раздел. Если просто нужна помощь, то задавай более конкретные вопросы. Что именно не понятно или не знаешь как сделать?
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Bod_r
Сообщения: 8
Зарегистрирован: 14 мар 2010, 00:37

Re: Гауссовы целые числа

Сообщение Bod_r » 14 мар 2010, 01:25

незнаю как сделать :(

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Гауссовы целые числа

Сообщение Romeo » 14 мар 2010, 14:03

Ну раз уж ты поленился предоставить теорию для тех, кто не понимает (или забыл) что такое комплексное число или гауссово число (две буквы "с" обязательны), то теорию предоставлю я (ссылка на Википедию).

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

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

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

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

Пробуй реализовать и задавай вопросы, если что-то не будет получаться. Будем помогать. Если передумал писать сам, то дай знать и я перенесу в раздел заказов.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Bod_r
Сообщения: 8
Зарегистрирован: 14 мар 2010, 00:37

Re: Гауссовы целые числа

Сообщение Bod_r » 14 мар 2010, 14:45

о) спасибо за информацию!
буду пробовать

Taras
Сообщения: 1
Зарегистрирован: 17 мар 2010, 15:00

Re: Гауссовы целые числа

Сообщение Taras » 17 мар 2010, 15:07

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

Bod_r
Сообщения: 8
Зарегистрирован: 14 мар 2010, 00:37

Re: Гауссовы целые числа

Сообщение Bod_r » 18 мар 2010, 00:25

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

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

Аватара пользователя
rrrFer
Сообщения: 224
Зарегистрирован: 07 сен 2008, 13:15
Контактная информация:

Re: Гауссовы целые числа

Сообщение rrrFer » 18 мар 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;
}
первая часть
Приглашаю на свой блог о программировании: pro-prof.com

Bod_r
Сообщения: 8
Зарегистрирован: 14 мар 2010, 00:37

Re: Гауссовы целые числа

Сообщение Bod_r » 19 мар 2010, 01:31

алгоритм продолжения я уже дописал ... позже выложу

Bod_r
Сообщения: 8
Зарегистрирован: 14 мар 2010, 00:37

Re: Гауссовы целые числа

Сообщение Bod_r » 21 мар 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;
}

Ответить