Czy z danych liczb można otrzymać sumę
Kod był wyświetlany 1704 razy.
    /*
  Name: Czy z danych liczb można otrzymać sumę
  Copyright: GPL GNU
  Author: Przemysław Pastuszka
  Date: 29-03-10 16:03
  Description: 
  Napisz algorytm, który dla danego zbioru S złożonego z n liczb całkowitych sprawdza, czy istnieją dwa elementy w S, których suma jest równa podanej zmiennej x.
  Przykłady:
  1. Wejście:
  Ile liczb? 8
  Podaj liczby: 22 1 88 6 99 7 5 36
  Podaj sume: 106
  Wyjście:
  TAK
  2. Wejście:
Ile liczb? 7
Podaj liczby: 5 9 11 23 88 61 2
Podaj sume: 21
Wyjście:
NIE
*/
#include <iostream>
#include <conio.h>
using namespace std;
void Scal(int tab[],int p, int q, int k)
{
	int dlugosc1=q-p+2, dlugosc2=k-q+1;
	int *L=new int[dlugosc1],*P=new int[dlugosc2];
	for(int i=0;i<dlugosc1-1;i++)
		L[i]=tab[p+i];
	for(int i=0;i<dlugosc2-1;i++)
		P[i]=tab[q+i+1];
	L[dlugosc1-1]=P[dlugosc2-1]=32000;
	int a=0,b=0;
	for(int i=p;i<=k;i++)
		if(L[a]<P[b])
			tab[i]=L[a++];
		else
			tab[i]=P[b++];
}
void Sortuj(int tab[], int p, int k)
{
	if(p<k)
	{
		int q=(k+p)/2;
		Sortuj(tab,p,q);
		Sortuj(tab,q+1,k);
		Scal(tab,p,q,k);
	}
}
int main()
{
	cout<<"Ile liczb? ";
	int n,x;
	cin>>n;
	int *tablica=new int[n];
	cout<<"Podaj liczby: ";
	for(int i=0;i<n;i++)
		cin>>tablica[i];
	cout<<"Podaj sume: ";
	cin>>x;
	Sortuj(tablica,0,n-1);
	bool czy=false;
	for(int i=0;i<n;i++)
	{
		int p=i+1,k=n-1;
		while(p<=k)
		{
			int q=(p+k)/2;
			if(tablica[i]+tablica[q]==x)
			{
				czy=true;
				break;
			}
			if(p==k)
				break;
			if(tablica[i]+tablica[q]<x)
				if(p==q)
					p=q+1;
				else
					p=q;
			else
				if(k==q)
					k=q-1;
				else
					k=q;
		}
		if(czy)
			break;
	}
	if(czy)
		cout<<"TAK";
	else
		cout<<"NIE";
	getch();
	return 0;
}    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT