Программа,исходник перебора слов, функций или чисел, удовлетворяющих заданным условиям языке программирования на Си(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