Bioinfo_Homework_01

2024-05-08

Purposes

1. 最大公约数计算：

通过比较暴力枚举法和辗转相除法，探讨不同算法在计算最大公约数时的效率和适用性，从而了解算法选择对于特定问题的影响。

2. 判断2的整数次幂：

通过穷举法、递归法和转化为二进制比较法，比较不同判断方法的准确性和执行效率，进一步理解算法设计中的考虑因素。

3. 寻找缺失的整数：

利用排序找不连续、5050减去数组累加和和哈希表等方法，分析不同算法在解决类似问题上的优劣，探讨算法复杂度和数据结构选择对解决问题的影响。

Codes


do# Rstudio Server URL: http://202.195.187.9:8787/
# 账号密码与Linux一致
# 切换R路径
.libPaths("/home/biotools/anaconda3/envs/R4.3.1/lib/R/")
################################################################################
# Q1: 求出两个整数的最大公约数
#############################
## A1.1: 暴力枚举法
maxNum = function(x,y){
  for (i in x:1){ # 取两个数之一, 从大到小遍历
    if (x %% i == 0 && y %% i == 0){ # 如果发现第一个公约数, 即为最大公约数
      return(i)
      break # 随即跳出循环
    }
  }
}

# 测试
maxNum(1000,64) # 输出为8
maxNum(16,100) # 输出为4

#############################
## A1.2 辗转相除法(递归算法)
zzxc = function(x,y){
  if (x%%y == 0){ # 如果恰好可以相互整除
    return(y) # 则直接返回被除数为两数的最大公约数
  }else{ # 如果不可以恰好整除
    return(zzxc(y,x%%y)) # 把被除数和余数再次代入函数
  }
}

# 测试
zzxc(1000,64)
zzxc(16,100)

################################################################################
# Q2: 判断一个正整数是否是2的整数次幂
#############################
## A2.1: 穷举法
power2_f1 = function(x){
  tmp = 1 # 设置2的指数
  while (tmp <= x){
    if (tmp == x){ # 如果找到与待判断数大小相同的2的整数次幂
      return(TRUE) # 则返回TRUE
    }
    tmp = tmp*2 # 一直循环, 2^1, 2^2, 2^3...
  }
  return(FALSE) # 如果不找到, 则返回FALSE
}

# 测试
power2_f1(1024)
power2_f1(1000)

#############################
## A2.2: 递归法 (一直除)
power2_f2 = function(x){
  if (x == 2) { # 如果一直除下去, 结果为2, 则返回TRUE
    return(TRUE)
  } else if (x > 2) { # 如果结果大于2
    return(power2_f2(x/2)) # 再次除以2, 再次代入函数
  } else { # 如果不符合, 则返回FALSE
    return(FALSE)
  }
}

# 测试
power2_f2(1024)
power2_f2(1000)

#############################
## A2.3: 转化为二进制比较
power2_f3 = function(x){
  # 首先将x和x-1转化为二进制, 执行位运算AND操作
  # 只有在两个输入序列中都为1时，结果序列的对应位置才为1，否则为0
  # 最后将上述位序列转换回整数形式, 并检查这个整数是否等于0
  a = (as.integer( intToBits(x) & intToBits(x-1) ) == 0);

  for (i in 1:length(a)){ # 遍历结果数组
    if (a[i] == FALSE){ # 只要发现有一个结果不是TRUE
      return(FALSE) # 说明原数不是2的整数次幂
    }
  }
  return(TRUE) # 如果结果全是TRUE, 则说明原数是2的整数次幂
}

# 测试
power2_f3(1024)
power2_f3(1000)

################################################################################
# Q3: 寻找缺失的整数
# 在一个无序数组中有99个正整数，范围是1--100，唯独缺少其中的1个整数。
# 如何找出这个缺失的整数？

# 随机选取99个数构成array (从1到100里面取)
array = sample(1:100, 99, replace = FALSE)

#############################
# A3.1: 排序找不连续
findInt_f1 = function(array){
  sorted_array = sort(array) # 数组排序
  for (i in 1:98){ # 遍历排序后的数组
    if (sorted_array[i+1]-sorted_array[i] != 1){
      # 如果右边的数减去左边的数不是1, 则返回左边的数加1为缺失的整数
      return(sorted_array[i]+1)
    }
  }
}

# 测试 
# (由于array为随机选取, 每次重新运行上面的sample()会导致结果不同)
findInt_f1(array)

#############################
## A3.2: 5050减去array的累加和
findInt_f2 = function(array){
  array_sum = sum(array) # 求array的和
  return(5050-array_sum) # 返回值: 5050减去array的和则为缺失的整数
}

# 测试
# (由于array为随机选取, 每次重新运行上面的sample()会导致结果不同)
findInt_f2(array)

#############################
## A3.3: 哈希表
# 服务器已安装hash包
# install.packages("hash")
findInt_f3 = function(array){
  library(hash) # 引入hash包
  h = hash() # 创建一个哈希表
  for (i in 1:100){ # 添加键值对
    h[[as.character(i)]] = i #键值必须为字符类型
  }
  for (j in 1:99){ # 删除哈希表里面含有array对应的键值对
    del(as.character(array[j]),h)
  }
  keys(h) # 剩下的最后一个键值就是缺失的数字
}

# 测试
# (由于array为随机选取, 每次重新运行上面的sample()会导致结果不同)
findInt_f3(array)

Results


##########################
# Q1: 求出两个整数的最大公约数
##########################
## A1.1: 暴力枚举法
> maxNum(1000,64)
[1] 8
> maxNum(16,100)
[1] 4

## A1.2 辗转相除法(递归算法)
> zzxc(1000,64)
[1] 8
> zzxc(16,100)
[1] 4

################################
# Q2: 判断一个正整数是否是2的整数次幂
################################
## A2.1: 穷举法
> power2_f1(1024)
[1] TRUE
> power2_f1(1000)
[1] FALSE

## A2.2: 递归法 (一直除)
> power2_f2(1024)
[1] TRUE
> power2_f2(1000)
[1] FALSE

## A2.3: 转化为二进制比较
> power2_f3(1024)
[1] TRUE
> power2_f3(1000)
[1] FALSE

##################
# Q3: 寻找缺失的整数
##################

> # (由于array为随机选取, 每次重新运行上面的sample()会导致结果不同)
> findInt_f1(array)
[1] 37

> # (由于array为随机选取, 每次重新运行上面的sample()会导致结果不同)
> findInt_f2(array)
[1] 37

> # (由于array为随机选取, 每次重新运行上面的sample()会导致结果不同)
> findInt_f3(array)
[1] "37"

Purposes

1. 最大公约数计算：

2. 判断2的整数次幂：

3. 寻找缺失的整数：

Codes

Results

Contents