Category: Algorithm

heapのpushとpop

fn push(x: i32) {
   let mut heap = [1, 2, 3, 4, 5, 6, 7, 8];
   let sz = 0;
   let mut i = sz + 1;

   while(i > 0) {
      let p = (i -1) / 2;

      if heap[p] <= x {
         break;
      }

      heap[i] = heap[p];
      i = p;
   }
   heap[i] = x;
}

fn pop() {
   let mut heap = [1, 2, 3, 4, 5, 6, 7, 8];
   let sz = 0;

   let ret = heap[0];
   let x = heap[heap.len() -1];

   let mut i = 0;
   while(i * 2 + 1 < sz) {
      let mut a = i * 2 + 1;
      let mut b = i * 2 + 2;
      if (b < sz && heap[b] < heap[a]) {
         a = b;
      }
      if (heap[a] >= x) {
         break;
      }

      heap[i] = heap[a];
      i = a;
   }
   heap[i] = x;
}

dynamic programing

use std::collections::HashMap;

fn rec (i: i32, j: i32) -> i32{

   let n = 4;
   let w = [
      [2,3],
      [1,2],
      [3,4],
      [2,2]
   ];
   let res;
   if(i == n) {
      res = 0;
   } else if (j < w[i as usize][0]) {
      res = rec(i + 1, j);
   } else {
      res = std::cmp::max(rec(i + 1, j), rec(i + 1, j - w[i as usize][0]) + w[i as usize][1]);
   }
   return res;
}

fn main() {
   let W = 5;
   let res = rec(0, W);
   println!("{}", res);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.52s
Running `target/debug/basic`
7

hashmapではなく、多次元配列にする必要あり

Lake Counting 2386

const N: i32 = 10;
const M: i32 = 12;

fn dfs(x: i32, y: i32) {
   field[x][y] = ".".to_string();

   for (let dx in -1..1) {
      for (let dy in -1..1) {
         let nx = x + dx;
         let ny = y + dy;

         if(0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') {
            dfs(nx, ny);
         }
      }
   }
}


fn main() {
   let field[N, M];
   let mut res = 0;
   for i in 0..N {
      for j in 0..M {
         if field[i][j] == 'W' {
            dfs(i, j);
            res =+ 1;
         }
      }
   }
   println!("{}", res);
}

全探索

fn dfs(i: i32, sum: i32) -> bool {
   let k = 10;
   let n = 10;

   if (i == n) {
      return sum == k;
   }

   if (dfs(i + 1, sum)) {
      return true;
   }

   if (dfs(i + 1, sum + i)) {
      return true;
   }
   return false;
}


fn main() {
   if (dfs (0, 0)) {
      println!("yes");
   } else {
      println!("no");
   }
}

Ants POJ 1852

fn main() {
   let n = 10;
   let L = 100;
   let mut minT: i32 = 0;

   for i in 0..n {
      minT = std::cmp::max(minT, i.min(L - i));
   }

   let mut maxT: i32 = 0;
   for i in 0..n {
      maxT = std::cmp::max(minT, std::cmp::max(i, L - i));
   }

   println!("max:{}, min: {}", minT, maxT);

}

max:9, min: 91

【Rust】ルックアップテーブル【アルゴリズム】

fn main() {

   let Q = [
      100, 200, 250, 300, 360
   ];

   let R = [
      401, 302, 101, 102, 301
   ];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let x  = x.trim_end().to_owned();
   let a = x.parse::<i32>().unwrap();

   let n = Q.len();

   while a > 0 {
      let mut i = 0;
      while i < n {
         if a < Q[i] {
            println!("整理番号{}番の方は{}会場です。", a, R[i]);
            i = n;
         } else {
            i += 1;
         }

      }
   }
}

整理番号100番の方は302会場です。

### 選択ソート

fn main() {

   let A = [
      84, 121, 43, 93, 140, 83, 14, 93, 181, 58
   ];

   let n = A.len();
   seq_sort(n, A);
}

fn seq_sort(n: usize, mut A: [i32; 10]) {
   let mut i = 0;
   let mut B: [i32; 10] = [0; 10];
   let mut k;
   for i in 0..n {
      
      let mut a = 999;
      let mut j = 0;
      for j in j..n {
         if a > A[j] {
            a = A[j];
            k = j;
         }
      }
      A[k] = 999;
      B[i] = a;
   }
   
}

【Rust】バイナリーサーチ【アルゴリズム】

fn main() {

   let mut commodity: [String; 8] = [
      "ジュース".to_string(),
      "紅茶".to_string(),
      "アイスティ".to_string(),
      "コーヒー".to_string(),
      "アイスコーヒー".to_string(),
      "ショートケーキ".to_string(),
      "チーズケーキ".to_string(),
      "トースト".to_string(),
   ];

   let mut price: [i32; 8] = [
      280, 300, 320, 350, 370, 550, 600, 650
   ];

   let mut x = String::new();
   std::io::stdin().read_line(&mut x).expect("Failed to read line");
   let x  = x.trim_end().to_owned();
   let a = x.parse::<i32>().unwrap();

   let n = commodity.len() as i32;
   bin_search(a, n, price);
   // seq_search();
}

fn bin_search(a: i32, n: i32, price: [i32; 8]) {
   let mut p = -1;
   let mut l = 0;
   let mut h = n - 1;

   while (l <= h && p == -1) {
      if (a > price[((l+h) / 2) as usize]) {
         l = (l + h) / 2 + 1;
      } else {
         if (a == price[((l+h)/2) as usize]) {
            p = (l +h) / 2;
         } else {
            h = (l + h) / 2 - 1;
         }
      }
   }
   println!("{}", p);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
Running `target/debug/basic`
300
1

【Rust】素数: エラトスネテスのふるい【アルゴリズム】

fn main() {

   let mut s: [i32; 101] = [1; 101];

   let mut i = 2;
   while i <= 100 {
      s[i] = 1;
      i += 1;
   }

   i = 2;
   while i * i <= 100 {
      let mut j = 2;

      while i * j <= 100 && s[i]!= 0 {
         s[i*j] = 0;
         j += 1;
      }
      i += 1;
   }

   i = 2;
   while i < 100 {
      if s[i] == 1 {
         println!("{}", i);
      }
      i += 1;
   }
}

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

紀元前の話

【Rust】素数【アルゴリズム】

fn main() {

   let mut s: [i32; 100] = [0; 100];

   let mut i = 1;
   s[0] = 2;

   let mut n = 3;
   let mut j = 0;
   while n <= 100 {
      let quotient = n / s[j];
      let reminder = n % s[j];

      if reminder == 0 {
         n = n + 2;
         j = 1;
      } else {
         if quotient >= s[j] {
            j += 1;
         } else {
            s[j] = n;
            i += 1;
            j = 1;
            n = n + 2;
         }
      }
   }

   let mut i = 0;
   while s[i] != 0 {
      println!("{}", s[i]);
      i += 1;
   }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.40s
Running `target/debug/basic`
thread ‘main’ panicked at src/main.rs:11:22:
attempt to divide by zero
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

整数を”0″で割るとundefinedでエラーになる。。。
うーん　どう表現したら良いんやろうか