Category: algorithm

変数を用意しておいて、最大値、最小値の値を更新していくだけですね。
ループを抜けるのは10000以上か0以下としています。

fn main() {

   let mut imax: i32 = -1;
   let mut imin: i32 = 10000;
   let mut kmax: i32 = 0;
   let mut kmin: i32 = 0;
   let mut k: i32 = 0;
   let mut i: i32 = 0;

   while(i >= 0 && i <= 9999){
      println!("4桁以内の正の整数を入力してください。");
      let mut x = String::new();
      std::io::stdin().read_line(&mut x).expect("Failed to read line");
      x = x.trim_end().to_owned();
      i = x.parse::<i32>().unwrap();
      if (0 < i && i < 10000) {
         k += 1;
         if(imax < i) {
            imax = i;
            kmax = k;
         }

         if(imin > i) {
            imin = i;
            kmin = k;
         }
      }
   }

   if (k == 0) {
      println!("入力されていません。");
   } else {
      println!("最大値 {}({}回目)", imax, kmax);
      println!("最小値 {}({}回目)", imin, kmin);
   }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.90s
Running `target/debug/basic`
4桁以内の正の整数を入力してください。
100
4桁以内の正の整数を入力してください。
20
4桁以内の正の整数を入力してください。
50
4桁以内の正の整数を入力してください。
29
4桁以内の正の整数を入力してください。
829
4桁以内の正の整数を入力してください。
2222
4桁以内の正の整数を入力してください。
2452
4桁以内の正の整数を入力してください。
11245
最大値 2452(7回目)
最小値 20(2回目)

うーむ　なるほど〜

偶数の和の場合は、n += 2;とする

fn main() {

   let mut n: i32 = 1;
   let mut t: i32 = 0;

   while n <= 100 {
      t = t + n;
      n += 1;
   }
   println!("{}", t);
}

fn main() {

   println!("入力されたmからnまでの合計を求めます。二つの数字を入力してください。");
   let mut x = String::new();
   let mut y = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   x = x.trim_end().to_owned();
   let mut x: i32 = x.parse::<i32>().unwrap();
   std::io::stdin().read_line(&mut y).expect("Failed to read line");
   y = y.trim_end().to_owned();
   let mut y: i32 = y.parse::<i32>().unwrap();
   
   if x > y {
      println!("mの方が大きいです。")
   }
   let mut w: i32 = 0;
   while x <= y {
      w = w + x;
      x += 1;
   }
   println!("mからnまでの合計値は{}", w);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.38s
Running `target/debug/basic`
入力されたmからnまでの合計を求めます。二つの数字を入力してください。
2
5
mからnまでの合計値は14

ユークリッド互助法

fn main() {

   println!("最大公約数を求めます。二つの数字を入力してください。");
   let mut x = String::new();
   let mut y = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   x = x.trim_end().to_owned();
   let mut x: i32 = x.parse::<i32>().unwrap();
   std::io::stdin().read_line(&mut y).expect("Failed to read line");
   y = y.trim_end().to_owned();
   let mut y: i32 = y.parse::<i32>().unwrap();
   
   let mut a: i32;
   let mut b: i32;
   let mut r: i32;
   if (x > y) {
      a = x;
      b = y;
   } else {
      a = y;
      b = x;
   }

   r = a % b;

   while (r != 0) {
      a = b;
      b = r;
      r = a % b;
   }
   println!("最大公約数は{}", b);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.18s
Running `target/debug/basic`
最大公約数を求めます。二つの数字を入力してください。
100
75
最大公約数は25

fn main() {

   println!("数字を入力してください。");
   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   x = x.trim_end().to_owned();
   let x: i32 = x.parse::<i32>().unwrap();

   if x > 100 {
      println!("{}は100より大きい", x);
   } else {
      println!("{}は100より小さい", x);
   }
}

最小値

fn main() {

   let a = 10;
   let b = 15;
   let c = 9;
   let mut w: i32;

   if a <= b {
      if a <= c {
         w = a;
      } else {
         w = c;
      }
   } else {
      if b <= c {
         w = b;
      } else {
         w = c;
      }
   }
   println!("{}", w);
}

Rustにはstd::cmp::minという関数があるが、argmentは2つでないといけない
https://doc.rust-lang.org/std/cmp/fn.min.html
std::cmp::min(a, b, c);とは書けない。

fn main() {

   let a = 10;
   let b = 15;
   let c = 9;
   let mut w: i32;
   
   if(a <= b && a <= c) {
      w = a;
   } else if (a <= b && a > c) {
      w = c;
   } else if (a > b && b <= c) {
      w = b;
   } else {
      w = c;
   }
   println!("{}", w);
}

計算量を少なくする方法

fn main() {

   let a = 10;
   let b = 15;
   let c = 9;
   let mut w: i32;
   
   w = a;
   if(b < w) {
      w = b;
   }
   if (c < w) {
      w = c;
   }
   println!("{}", w);
}

大文字小文字

fn main() {

   println!("一文字入力してください。");
   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   x = x.trim_end().to_owned();
   let char_vec: Vec<char> = x.chars().collect();
   for y in char_vec {
      if y.is_uppercase() {
         println!("大文字です");
      } else {
         println!("子文字です");
      }
   }
}

mem::swap(&mut x, &mut y);でswapできる。
https://doc.rust-lang.org/std/mem/fn.swap.html

use std::mem;

fn main() {

   println!("二つの数字を入力してください。");
   let mut x = String::new();
   let mut y = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   x = x.trim_end().to_owned();
   std::io::stdin().read_line(&mut y).expect("Failed to read line");
   y = y.trim_end().to_owned();

   mem::swap(&mut x, &mut y);
   println!("入力した値をswapすると「{}」と「{}」です", x, y);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.39s
Running `target/debug/basic`
二つの数字を入力してください。
20
15
入力した値をswapすると「15」と「20」です

既に用意されているのね…

### 単純に計算していく方法

fn main() {
    
    let mut vote = [
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let n = vote.len();

    let half = n / 2;
    let mut winner = "".to_string();

    for i in 0..n {
        if vote[i] == "" {
            continue;
        }

        let mut count = 1;

        for j in i+1..n {
            if vote[j] == vote[i] {
                count += 1;
                vote[j] = "".to_string();
                if count > half {
                    winner = vote[i].clone();
                    break;
                }
            }
        }
        if winner != "".to_string() {
            break;
        }
    }

    if winner != "".to_string() {
        println!("{}が過半数を取りました", winner);
    } else {
        println!("過半数を取った人はいません");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/basic`
鈴木花子が過半数を取りました

### ボイアーとムーアのアルゴリズム
最初に最も多い組み合わせを調べ、それが過半数に達しているか計算する。
計算量が少なくて済む。

fn main() {
    
    let vote = [
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let n = vote.len();
    let mut candidate = "".to_string();

    let mut survivor = 0;

    for i in 0..n {
        if survivor == 0 {
            candidate = vote[i].clone();
            survivor = 1;
        } else if candidate == vote[i] {
            survivor += 1;
        } else {
            survivor -= 1;
        }
    }
    let mut count = 0;
    if survivor != 0 {
        for i in 0..n {
            if candidate == vote[i] {
                count += 1;
            }
        }
    }

    if count > (n / 2) {
        println!("{}が過半数を取りました。", candidate);
    } else {
        println!("過半数を取った人はいません。");
    }
}

### ソートによるカウント
ソートして真ん中の値のカウントをする。これも美しい。

fn main() {
    
    let mut vote = vec![
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let half = vote.len() / 2;

    vote.sort();

    if vote.clone().into_iter().filter(|n| *n == vote[half]).count() > half {
        println!("{}が過半数を取りました。", vote[half]);
    } else {
        println!("過半数を取った人はいません。");
    }
}

### hashmapで計算する

use std::collections::HashMap;

fn main() {
    
    let vote = [
        "山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), 
        "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), 
        "鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(), 
    ];

    let mut blackboard: HashMap<String, i32> = HashMap::new();

    for v in vote.clone() {
        if !blackboard.contains_key(&v) {
            blackboard.insert(v.clone(),1);
        } else {
            blackboard.insert(v.clone(), 1 + blackboard[&v]);
        }
        println!("{:?}", blackboard);
    }

    let key_with_max_value =blackboard.iter().max_by_key(|entry | entry.1).unwrap();
    if *key_with_max_value.1 as usize > (vote.len() / 2) {
        println!("過半数を取得しました。{:?}", key_with_max_value);
    } else {
        println!("過半数を取った人はいません。");
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/basic`
{“山田太郎”: 1}
{“山田太郎”: 1, “鈴木花子”: 1}
{“山田太郎”: 1, “鈴木花子”: 1, “佐藤三郎”: 1}
{“佐藤三郎”: 1, “山田太郎”: 1, “鈴木花子”: 2}
{“佐藤三郎”: 1, “山田太郎”: 1, “鈴木花子”: 3}
{“佐藤三郎”: 2, “山田太郎”: 1, “鈴木花子”: 3}
{“佐藤三郎”: 2, “山田太郎”: 1, “鈴木花子”: 4}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 4}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 5}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 6}
{“佐藤三郎”: 3, “山田太郎”: 2, “鈴木花子”: 6}
{“佐藤三郎”: 3, “山田太郎”: 2, “鈴木花子”: 7}
過半数を取得しました。(“鈴木花子”, 7)

これが感覚的には一番わかりやすい。でもアルゴリズム的にはボイヤーの方が優れているんだよなー

fn leap_year(year: u32) -> bool {
    if year % 4 == 0 && year % 100 != 0 || year % 400 == 0 {
        return true;
    } 
    false
}

fn day_of_week(year: usize, month: usize) -> usize {
    let mut days_of_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

    if leap_year(year.try_into().unwrap()) {
        days_of_month[2] = 29;
    }

    let day = 1;
    let mut days = 0;

    for y in 1..year {
        if leap_year(y.try_into().unwrap()) {
            days += 366
        } else {
            days += 365
        }
    }

    for m in 1..month {
        days += days_of_month[m as usize]
    }

    days += day;
    return days % 7
}

fn main() {
    let days_of_week_name = ["日".to_string(), "月".to_string(),"火".to_string(),"水".to_string(),"木".to_string(),"金".to_string(),"土".to_string()];

    let mut days_of_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    let year = 2040;
    let month = 3;

    if leap_year(year.try_into().unwrap()) {
        days_of_month[2] = 29;
    }
    let first_day = day_of_week(year, month);

    println!("{}年 {}月", year, month);
    println!("日 月 火 水 木 金 土");
    let emp = " ".to_string();

    print!("{}", emp.repeat(first_day*3));
    for day in 1..(1 + days_of_month[month]) {
        print!("{:<2} ", day);
        if(day + first_day - 1) % 7 == 6 {
            print!("\n");
        }
    }
    print!("\n");
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.14s
Running `target/debug/basic`
2040年 3月
日 月 火 水 木 金 土
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

これは中々面白い！！！　そんなに難しくないけど、中々思いつかない!

4回くじを引くという条件から、nパターンの4回分を全通り試して、一致する組み合わせを探している。
全通りを探す場合、ループの中でループをするという書き方が多い。

static MAX_N: usize = 50;

fn main() {
    let mut n: i32;
    let mut m: i32;
    let mut k: Vec<i32> = Vec::new();

    println!("紙の枚数 n を入力してください。");
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let n = line.trim().parse::<i32>().unwrap();
    println!("期待する数字の和 m を入力してください。");
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let m = line.trim().parse::<i32>().unwrap();

    println!("紙に書かれている数字をそれぞれ入力してください。");
    for i in 0..n {
        println!("{}番目の数字:", i + 1);
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        let n = line.trim().parse::<i32>().unwrap();
        k.push(n);
    }

    let mut flg = false;

    for a in 0..n {
        for b in 0..n {
            for c in 0..n {
                for d in 0..n {
                    if k[a as usize] + k[b as usize] + k + k[d as usize] == m {
                        flg = true;
                        println!("発見! 組み合わせは{},{},{},{}", k[a as usize], k[b as usize], k, k[d as usize]);
                    }
                }
            }
        }
    }

    if !flg {
        println!("そのような組み合わせはありません。");
    }
}

紙の枚数 n を入力してください。
3
期待する数字の和 m を入力してください。
10
紙に書かれている数字をそれぞれ入力してください。
1番目の数字:
3
2番目の数字:
3
3番目の数字:
2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,3,2,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,3,2
発見! 組み合わせは3,2,2,3
発見! 組み合わせは3,2,2,3
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,3,2
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,3,2,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3
発見! 組み合わせは2,2,3,3

ここでは東北、秋田、山形新幹線の駅からそれぞれ一つづつランダムに駅を抽出する組み合わせを出力するという簡易的な実装例とする。
実際のどこかにビューーン!は、更に上越、北陸新幹線もあり、候補47駅、5つの新幹線の中から4つの駅を出力しているので、若干ロジックが異なるが、考え方はおおよそ同じだ。※[東北、秋田、山形、上越、北陸]から、4つをランダムに抽出して、そこから更にランダムに抽出しているのかもしれない。

サーバ側では、各駅がどの新幹線駅かというデータを持っておき、iteratorからfilterでそれぞれの新幹線ごとにvectorに入れて、そこからランダムに抽出する。下のサンプルでは、最後に往復料金でソートしてprintln!している。

use rand::prelude::IndexedRandom;

#[derive(Debug, Clone)]
struct Destination {
    bullet_train: String,
    station: String,
    ticket_price: u32
}

fn main() {
    let data = [
        Destination{ bullet_train: "東北".to_string(), station: "那須塩原".to_string(), ticket_price: 12040},
        Destination{ bullet_train: "東北".to_string(), station: "新白河".to_string(), ticket_price: 13580},
        Destination{ bullet_train: "東北".to_string(), station: "郡山".to_string(), ticket_price: 16680},
        Destination{ bullet_train: "東北".to_string(), station: "福島".to_string(), ticket_price: 18220},
        Destination{ bullet_train: "東北".to_string(), station: "白石蔵王".to_string(), ticket_price: 21080},
        Destination{ bullet_train: "東北".to_string(), station: "仙台".to_string(), ticket_price: 22180},
        Destination{ bullet_train: "東北".to_string(), station: "古川".to_string(), ticket_price: 23280},
        Destination{ bullet_train: "秋田".to_string(), station: "雫石".to_string(), ticket_price: 32200},
        Destination{ bullet_train: "秋田".to_string(), station: "田沢湖".to_string(), ticket_price: 32640},
        Destination{ bullet_train: "秋田".to_string(), station: "角館".to_string(), ticket_price: 34040},
        Destination{ bullet_train: "秋田".to_string(), station: "大曲".to_string(), ticket_price: 34700},
        Destination{ bullet_train: "秋田".to_string(), station: "秋田".to_string(), ticket_price: 36040},
        Destination{ bullet_train: "山形".to_string(), station: "米沢".to_string(), ticket_price: 21060},
        Destination{ bullet_train: "山形".to_string(), station: "高畠".to_string(), ticket_price: 21500},
        Destination{ bullet_train: "山形".to_string(), station: "赤湯".to_string(), ticket_price: 22240},
        Destination{ bullet_train: "山形".to_string(), station: "かみのやま温泉".to_string(), ticket_price: 22900},
        Destination{ bullet_train: "山形".to_string(), station: "さくらんぼ東根".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "村山".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "大石田".to_string(), ticket_price: 24900},
        Destination{ bullet_train: "山形".to_string(), station: "新庄".to_string(), ticket_price: 26000},
    ];

    let mut JR_Voom = Vec::new();

    let tohoku: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "東北")
        .collect();
    JR_Voom.push(tohoku.choose(&mut rand::thread_rng()).unwrap());

    let akita: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "秋田")
        .collect();
    JR_Voom.push(akita.choose(&mut rand::thread_rng()).unwrap());

    let yamagata: Vec<Destination> = data.clone().into_iter()
        .filter(|d|d.bullet_train == "山形")
        .collect();
    JR_Voom.push(yamagata.choose(&mut rand::thread_rng()).unwrap());
    JR_Voom.sort_by(|a, b| a.ticket_price.cmp(&b.ticket_price));

    for (i, destination) in JR_Voom.iter().enumerate() {
        println!("{:}: {}駅 (往復{}円)", i + 1, destination.station, destination.ticket_price);
    }
    
}

何度か実行すると以下のようになる。うん、見たことある光景である。
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.55s
Running `target/debug/app`
1: 郡山駅 (往復16680円)
2: 新庄駅 (往復26000円)
3: 秋田駅 (往復36040円)

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.08s
Running `target/debug/app`
1: 米沢駅 (往復21060円)
2: 古川駅 (往復23280円)
3: 雫石駅 (往復32200円)

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.16s
Running `target/debug/app`
1: 福島駅 (往復18220円)
2: 米沢駅 (往復21060円)
3: 田沢湖駅 (往復32640円)

プログラムでランダムに抽出しているだけだが、これに一喜一憂しているのだからしょうがない。多分、●●駅の方が△△駅よりも出やすくするといった駅によっての重み付とかはないと思うが、実際のところは分かりません。。

use std::io::stdin;

fn main() {

    let mut memory = Memory {
        slots: vec![0.0; 10],
    }
    let mut prev_result: f64 = 0.0;
    for line in stdin().lines() {
        let line = line.unwrap();
        if line.is_empty() {
            break;
        }

        let tokens: Vec<&str> = line.split(char::is_whitespace).collect();

        let is_memory = tokens[0].starts_with("mem");
        if is_memory && tokens[0].ends_with('+') {
            add_and_print_memory(&mut memory, tokens[0], prev_result);
            continue;
        } else if is_memory && tokens[0].ends_with('-') {
            add_and_print_memory(&mut memory, tokens[0], -prev_result);
            continue;
        }

        let left = eval_token(tokens[0], &memory);
        let right = eval_token(tokens[2], &memory);
        let result = eval_expression(left, tokens[1], right);
        print_output(result);

        prev_result = result;
    }
}

struct Memory {
    slots: Vec<f64>,
}

fn add_and_print_memory(memory: &mut Memory, token: &str, prev_result: f64) {
    let slot_index: usize = token[3..token.len() - 1].parse().unwrap();
    memory.slots[slot_index] += prev_result;
    print_output(memory.slots[slot_index]);
}
fn eval_token(token: &str, memory: &Memory) -> f64 {
    if token.starts_with("mem") {
        let slot_index: usize = token[3..].parse().unwrap();
        memory.slots[slot_index]
    } else {
        token.parse().unwrap()
    }
}
fn eval_expression(left: f64, operator: &str, right: f64) -> f64 {
    match operator {
        "+" => left + right,
        "-" => left - right,
        "*" => left * right,
        "/" => left / right,
        _ => {
            unreachable!()
        }
    }
}
fn print_output(value: f64) {
    println!(" => {}", value);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.49s
Running `target/debug/app`
1 + 2
=> 3
mem1+
=> 3
3 + 4
=> 7
mem2-
=> -7
mem1 * mem2
=> -21