LCME Четверг, 28.03.2024, 19:19
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: anatoliy  
Форум » Домашние задания » Программирование » Домашнее задание от 11.02 (Двоичная сортировка вставками)
Домашнее задание от 11.02
freidomДата: Понедельник, 15.02.2010, 22:20 | Сообщение # 1
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: Offline
1. Реализовать сортировку бинарными вставками
2. Найти n: log n! <> кол-ву сравнений бинарными вставками
3. Дан рюкзак объемом V и n предметов, с массой w_i и объемом v_i.
Найти такой набор индексов p1...pm, что sum (w_pi) - максимальна, и sum (v_pi) <= v.
Прикрепления: binary.ml (0.7 Kb)
 
froci9rgevkaДата: Вторник, 16.02.2010, 00:45 | Сообщение # 2
Лейтенант
Группа: Проверенные
Сообщений: 71
Репутация: 1
Статус: Offline
ещё не доделал, выкладываю чтобы не носить флэшку прошу не стирать...
open List;;
(* (a,b) a- обьём
b- масса *)

let v = 1.;;
let z = [(1.,2.);(2.,3.);(3.,4.)];;

let ro (a,b) = (a,b,b/.a);;

let rec plotnost l =
match l with
(a,b)::ls-> (a,b,b/.a)::(plotnost ls)
|[]->[];;
let z = plotnost z;;

let rec ubrat (a,b,c) m =
match m with
(a',b',c')::ms -> if a'=a && b'=b then ms else (a',b',c')::(ubrat (a,b,c) ms)
|[]->[];;

(* печать списка*)
let rec printf l =
Printf.printf "%s" "[";
(match l with
(a,b,c)::ls-> Printf.printf "%s" "("; Printf.printf "%d" (int_of_float a); Printf.printf "%s" ",";
Printf.printf "%d" (int_of_float b); Printf.printf "%s" ")"; Printf.printf "%s" ";"; printf ls
|[]->Printf.printf "%s" "]" );;

(* по кол-ву элементов в ранце выдаёт кол-во элементов которы ещё остались *)
let rec ostalnoe l =
let rec ostalnoe' m l =
match l with
(a,b,c)::ls-> ostalnoe' (ubrat (a,b,c) m) ls
|[] ->m in
ostalnoe' z l;;

(* печать списка*)
let rec print_para l =
match l with
(a,b,c)::ls -> print_float a; print_string ", "; print_float b; print_string ", ";
print_float c; print_string "\n"; print_para ls
|[]->[];;

(* сумма обйомов *)
let rec summa_obiom l =
match l with
(a,b,c)::ls -> a+.(summa_obiom ls)
|[]->0.;;

(* сумма масс *)
let rec summa_mass l =
match l with
(a,b,c)::ls -> b+.(summa_mass ls)
|[]->0.;;

(*допустимое решение*)
let rec optimal l n =
match l with
(a,b,c)::ls -> if (a+.(summa_obiom n))>v then optimal ls n else optimal ls ((a,b,c)::n)
|[]->n;;
let i = ref 0.(*(summa_mass (optimal z []))*);;

(*проверяет имеет ли смысл продолжение дерева
m- сколько предметов уже в рюкзаке
l- сколько ещё есть*)
let obiom' m =
let rec obiom' m l =
(* Printf.printf "%d" (int_of_float (summa_mass m)); Printf.printf "%s" "\n";*)
match l with
(a,b,c)::ls -> if (summa_obiom ((a,b,c)::m))>=v
then (if (summa_mass ((0.,c*.(v-.(summa_obiom m)),c)::m))>(!i)
then true else false)
else (obiom' ((a,b,c)::m) ls)
|[]->true in
obiom' m (ostalnoe m);;

(* строит дерево
m- сколько предметов уже в рюкзаке
l- сколько ещё есть *)
let rec proverka m n =
let l = (ostalnoe m) in Printf.printf "%d" (length l); Printf.printf "%s" "\n"; printf m; Printf.printf "%s" "\n"; (for n=0 to (length l)-1 do proverka ((nth l n)::m) (n-1) done;)
;;
(*
printf (ostalnoe m); Printf.printf "%s" "\n";
(if (summa_obiom m)<v then (if obiom' m then proverka' m (ostalnoe m));
(if (!i)<(summa_mass m) then i:=(summa_mass m)))
and
proverka' m l =
match l with
l1::ls -> proverka m ([l1]@m); proverka' m ls
|[]-> i:=(!i);;

print_float (!i);;
print_string "\n";;
if obiom' [ro (1.,2.)] then print_string "true" else print_string "false";;
*)proverka [] (length z -1);; (*
print_string "\n";;
print_float (!i);; *)

printf (ostalnoe [(ro (1.,2.));(ro (2.,3.))]);;


Саня - тащщи! XD

"If you have time to panic, you have time to be doing something productive" © Josh Whipple

You’re standing on your Bridle. Idiot! =)
© Roland “Slim” Simpson

Сообщение отредактировал froci9rgevka - Четверг, 18.02.2010, 01:13
 
Форум » Домашние задания » Программирование » Домашнее задание от 11.02 (Двоичная сортировка вставками)
  • Страница 1 из 1
  • 1
Поиск:

Copyright Freidom © 2024 Хостинг от uCoz