Программа,исходник перебора слов, функций или чисел, удовлетворяющих заданным условиям языке программирования на Си(C++)


Добавил:DMT
Дата создания:28 апреля 2008, 14:18
Дата обновления:28 апреля 2008, 14:18
Просмотров:6570 последний 29 ноября, 4:15
Комментариев: 0
Программа,исходник перебора слов, функций или чисел, удовлетворяющих заданным условиям языке программирования на Си(C++)
Каждое слово, функция или последовательность чисел выводится с новой строки. Числа m и n вводятся с клавиатуры.
Перебрать все сюръекции f:{0,1,…,m-1} ® {0,1,…,n-1}.

Описание алгоритма работы:
Перебираем все функции f:{0,1,…,m-1} ® {0,1,…,n-1} и если текущая функция является сюръекцией, то выводим ее на экран.
Текст программы: 
Код на C++
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. int m, n, *pos;
  5.  
  6. void GetNext()
  7. {
  8. 	pos[m - 1]++;
  9. 	for (int i = m - 1; i > 0; i--)
  10. 		if (pos[i] == n)
  11. 		{
  12. 			pos[i] = 0;
  13. 			pos[i - 1]++;
  14. 		}
  15. }
  16.  
  17. bool IsSur()
  18. {
  19. 	bool *exist = new bool[n], ret = true;
  20. 	for (int i = 0; i < n; i++) exist[i] = false;
  21. 	for (int i = 0; i < m; i++) exist[pos[i]] = true;
  22. 	for (int i = 0; i < m; i++)
  23. 		if (!exist[i])
  24. 		{
  25. 			ret = false;
  26. 			break;
  27. 		}
  28. 	delete[] exist;
  29. 	return ret;
  30. }
  31.  
  32. main()
  33. {
  34. 	int i, nums = 0;
  35. 	printf("Input m:"); scanf("%d", &m);
  36. 	printf("Input n:"); scanf("%d", &n);
  37. 	if (m < n)
  38. 	{
  39. 		printf("No Functions!\n");
  40. 		return;
  41. 	}
  42. 	pos = new int[m];
  43. 	for (i = 0; i < m; i++) pos[i] = 0;
  44. 	int max = pow(n, m);
  45. 	for (i = 0; i < max; i++)
  46. 	{
  47. 		if (IsSur())
  48. 		{
  49. 			for (int j = 0; j < m; j++)
  50. 				printf("%d ", pos[j]);
  51. 			printf("\n");
  52. 			nums++;
  53. 		}
  54. 		GetNext();
  55. 	}
  56. 	printf("Funcs: %d\n", nums);
  57. 	delete[] pos;
  58. }
  59.  
При использовании обязательна ссылка на http://DMTSoft.ru
up