今回は3週目の勉強会。アルゴリズムを勉強する。

• 全探索について

• Bit全探索について

• 二分探索について

勉強することになった。
次回は深さ優先探索・幅優先探索や素数判定やエイトクイーンなどをやろうと思っている。

前回👈👈👈

全探索について

参考

問題を解く (AtCoder)💪💪💪

Rust

use proconio::input;
fn main() {
    input! {
        n: i32,
    }

    for i in 1..=9 {
        for j in 1..=9 {
            if i * j == n {
                println!("Yes");
                return;
            }
        }
    }
    println!("No");
}

Python

def solve(n: int):
    for i in range(1, 10):
        for j in range(1, 10):
            if i*j == n:
                print('Yes')
                return
    print('No')

n = int(input())
solve(n)

Bit全探索について

参考

二分探索について

参考

問題を解く (AtCoder) 💪💪💪

Rust

fn main() {
    let mut nk = String::new();
    std::io::stdin().read_line(&mut nk).unwrap();
    let nk_vec: Vec<i32> = nk
        .split_whitespace()
        .map(|v| v.parse::<i32>().unwrap())
        .collect();
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    let vec: Vec<i32> = line
        .split_whitespace()
        .map(|str| str.parse::<i32>().unwrap())
        .collect();
    binary_search(&vec, *nk_vec.get(1).unwrap());
}

fn binary_search(a: &Vec<i32>, v: i32) {
    let mut left: usize = 0;
    let mut right: usize = a.len();
    while right - left > 1 {
        let mid = (right + left) / 2;
        if *a.get(mid).unwrap() >= v {
            right = mid;
            continue;
        }
        left = mid;
    }

    println!(
        "{}",
        if right != a.len() {
            right.to_string()
        } else {
            "-1".to_string()
        }
    );
}