Posted By

soulmachine on 03/24/09


Tagged

c mod


Versions (?)

给定n个整数,求一个最小的数,使得它们除以这个数的余数不重复


 / Published in: C
 

URL: http://www.yanjiuyanjiu.com

/** * @brief 给定n个整数,求一个最小的数,使得它们除以这个数的余数不重复 * @author soulmachine * @param[in] numbers 整数数组 * @param[in] count 整数个数 * @param[in] max_norm 模的最大值 * @return 成功返回大于0的最小模,失败返回0或-1 * @note 无 * @remarks 无 */

  1. /**
  2.  * @brief 给定n个整数,求一个最小的数,使得它们除以这个数的余数不重复
  3.  * @author soulmachine
  4.  * @param[in] numbers 整数数组
  5.  * @param[in] count 整数个数
  6.  * @param[in] max_norm 模的最大值
  7.  * @return 成功返回大于0的最小模,失败返回0或-1
  8.  * @note 无
  9.  * @remarks 无
  10.  */
  11. int decide_norm(int *numbers, int count, int max_norm)
  12. {
  13. int result = 0;
  14. int *bitmap = NULL; /* 存放第一次命中的数 */
  15. int norm = 0;
  16.  
  17. bitmap = (int*)malloc(max_norm * sizeof(int));
  18. if(NULL == bitmap)
  19. {
  20. result = -1;
  21. goto malloc_failed;
  22. }
  23.  
  24. for(norm = count; norm <= max_norm; ++norm)
  25. {
  26. int i = 0;
  27. memset(bitmap, 0, norm * sizeof(int));
  28. for(i = 0;i < count; i++)
  29. {
  30. int remainder = numbers[i] % norm;
  31. if(0 == bitmap[remainder])
  32. {
  33. bitmap[remainder] = numbers[i];
  34. }
  35. else
  36. {
  37. debug_printf("conflicted: %d %% %d = %d %% %d = %d\n", bitmap[remainder], norm, numbers[i], norm, remainder);
  38. break;
  39. }
  40. }
  41. if(count == i) /* 这个模下,各个数值没有冲突 */
  42. {
  43. result = norm;
  44. break;
  45. }
  46. }
  47.  
  48. malloc_failed:
  49. return result;
  50. }

Report this snippet  

You need to login to post a comment.