1005 继续(3n+1)猜想

简介: 1005 继续(3n+1)猜想

题目描述

点击直达题目链接

解题思路

两个思路:1.先排序,再剔除验证时重复的。2.先剔除验证时重复的,再排序。

剔除的规则是:除本身外,验证过程中发现相等的标记为0。

具体实现看代码

代码实现(以思路1为例)(本次以快排的方式实现

快速排序直达链接

#include <stdio.h>
#include <stdlib.h>
//快排,看不懂的上面有链接
void quick_sort(int* arr,int left,int right)
{
  int temp = arr[left];
  int a = left;
  int b = right;
  if (a >= b)
    return;
  while (a<b)
  {
    while (arr[b] <= temp&& a < b)
      b--;
    while (arr[a] >= temp && a < b)
      a++;
    //交换
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
  }
  arr[left] = arr[a];
  arr[a] = temp;
  quick_sort(arr, left, a-1);
  quick_sort(arr, b+1, right);
}

void delete(int* arr,int n)
{
  int i = 0,j=0;
  for (i=0;i<n;i++)
  {
    int temp = arr[i];
    while (temp != 1&&temp)//保证这个数不是0
    {
      if (temp % 2 == 0)
        temp /= 2;
      else
        temp = (temp* 3 + 1) / 2;
      for (j = 0; j < n; j++)
      {
        if (arr[j] == temp)
          arr[j] = 0;
      }
    }
  }
}
int main()
{
  int n;
  scanf("%d", &n);
  int* arr = (int*)malloc(n * sizeof(int));
  int i = 0;
  for (i=0;i<n;i++)
  {
    scanf("%d", arr + i);
  }
  //排序
  quick_sort(arr, 0, n - 1);
  //删除重复的
  delete(arr,n);
  //确定剩余几个数,目的是控制最后一个不打印空格
  int b = 0;
  for (i = 0; i < n; i++)
  {
    if (arr[i] == 0)
      b++;
  }
  b = n - b;
  //打印
  for (i=0;i<n;i++)
  {
    if (arr[i] != 0)
    {
      printf("%d", arr[i]);
      if (b-1)
      {
        printf(" ");
        b--;
      }
    }
  }
  free(arr);
  arr = NULL;
  return 0;
}

相关文章
|
2月前
|
算法
死磕-算法(一)
死磕-算法(一)
|
6月前
|
安全 测试技术
技术债是我们的错吗?
技术债是我们的错吗?
|
Java
hdu1279 验证角谷猜想
hdu1279 验证角谷猜想
54 0
|
算法
如何证明一个问题是VNP问题?计算机科学家找到了一种简单方法
如何证明一个问题是VNP问题?计算机科学家找到了一种简单方法
|
测试技术
1005 继续(3n+1)猜想 (25 分)
1005 继续(3n+1)猜想 (25 分)
90 0
|
测试技术
1001 害死人不偿命的(3n+1)猜想 (15 分)
1001 害死人不偿命的(3n+1)猜想 (15 分)
67 0
|
机器学习/深度学习
458. 可怜的小猪 : 进制猜想 & 香农熵验证
458. 可怜的小猪 : 进制猜想 & 香农熵验证
|
算法 程序员
弄懂“三门问题”,成功概率翻倍,来用代码验证一下
弄懂“三门问题”,成功概率翻倍,来用代码验证一下
253 0
弄懂“三门问题”,成功概率翻倍,来用代码验证一下