(C卷,100分)- 数字涂色(Java & JS & Python & C)

题目描述

疫情过后,希望小学终于又重新开学了,三年二班开学第一天的任务是将后面的黑板报重新制作。

黑板上已经写上了N个正整数,同学们需要给这每个数分别上一种颜色。

为了让黑板报既美观又有学习意义,老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。

现在请你帮帮小朋友们,算算最少需要多少种颜色才能给这N个数进行上色。

输入描述

第一行有一个正整数N,其中。

第二行有N个int型数(保证输入数据在[1,100]范围中),表示黑板上各个正整数的值。

输出描述

输出只有一个整数,为最少需要的颜色种数。

用例

输入

3
2 4 6

输出 1
说明 所有数都能被2整除
输入 4
2 3 4 9
输出 2
说明 2与4涂一种颜色,4能被2整除;3与9涂另一种颜色,9能被3整除。不能4个数涂同一个颜色,因为3与9不能被2整除。所以最少的颜色是两种。

题目解析

简单的逻辑题,题目要求:“同种颜色的所有数都可以被这种颜色中最小的那个数整除”。

因此我们可以直接将输入数列进行升序排序,则数列从左到右,元素依次增大,我们每次取最左边的数arr[i],然后遍历它后面的所有数arr[j]去除它,若可以整除,则为一种颜色,若不可以整除,则为不同颜色。

本题难点主要在于,如何标记一个元素已经涂色了,我这里直接定义了一个长度和输入数列arr相同的数组color,color所有元素默认未初始化,一旦arr[j]可以整除arr[i],则color[j] = true。

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = Integer.parseInt(sc.nextLine());

    int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    System.out.println(getResult(n, arr));
  }

  public static int getResult(int n, int[] arr) {
    Arrays.sort(arr);

    if (arr[0] == 1) {
      return 1;
    }

    boolean[] color = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
      if (color[i]) continue;

      color[i] = true;
      for (int j = i + 1; j < n; j++) {
        if (!color[j] && arr[j] % arr[i] == 0) {
          color[j] = true;
        }
      }

      count++;
    }

    return count;
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    let n = parseInt(lines[0]);
    let arr = lines[1].split(" ").slice(0, n);

    console.log(getMinColorCount(arr));

    lines.length = 0;
  }
});

function getMinColorCount(arr) {
  arr.sort((a, b) => a - b);

  if (arr[0] === 1) {
    return 1;
  }

  let color = new Array(arr.length);
  let count = 0;

  for (let i = 0; i < arr.length; i++) {
    if (color[i]) continue;
    color[i] = true;
    for (let j = i + 1; j < arr.length; j++) {
      if (!color[j] && arr[j] % arr[i] === 0) {
        color[j] = true;
      }
    }
    count++;
  }

  return count;
}

Python算法源码

# 输入获取
n = int(input())
arr = list(map(int, input().split()))


# 算法入口
def getResult():
    arr.sort()

    if arr[0] == 1:
        return 1

    color = [False]*n
    count = 0

    for i in range(n):
        if color[i]:
            continue

        color[i] = True
        for j in range(i+1, n):
            if not color[j] and arr[j] % arr[i] == 0:
                color[j] = True

        count += 1

    return count


# 调用算法
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

int getResult(int nums[], int nums_size);

int cmp(const void* a, const void* b) {
    return (*(int*) a)  - (*(int*) b);
}

int main() {
    int n;
    scanf("%d", &n);

    int nums[n];
    for(int i=0; i<n; i++) {
        scanf("%d", &nums[i]);
    }

    printf("%dn", getResult(nums, n));

    return 0;
}

int getResult(int nums[], int nums_size) {
    qsort(nums, nums_size, sizeof(int), cmp);

    if(nums[0] == 1) {
        return 1;
    }

    int* color = (int*) calloc(nums_size, sizeof(int));

    int count = 0;
    for(int i=0; i<nums_size; i++) {
        if(color[i]) continue;

        color[i] = 1;
        for(int j=i+1; j<nums_size; j++) {
            if(!color[j] && nums[j] % nums[i] == 0) {
                color[j] = 1;
            }
        }

        count++;
    }

    return count;
}

 

免责声明:

1、IT资源小站为非营利性网站,全站所有资料仅供网友个人学习使用,禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享,本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员,一律视为同意网站规定,本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

站点公告

没有账号?注册  忘记密码?