-
整数 向上取整算法:(x+n-1)/n
2013-09-30 11:29:59Floor表示向下取整 Ceiling表示向上取整 /* 1、假设变量x和n是两个正整数,我们知道x/n这个表达式的结果要取Floor, * 例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢? * 例如x是...Floor表示向下取整 Ceiling表示向上取整
/* 1、假设变量x和n是两个正整数,我们知道x/n这个表达式的结果要取Floor,
* 例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?
* 例如x是17,n是4,则结果是5;x是16,n是4,则结果是4。
*/
向上取整算法:(x+n-1)/n
解析:(1)当x/n正好除尽时,(x+n-1)/n=x/n+(n-1)/n=x/n
(2)当x/n除不尽时,余数肯定大于1,所以(x+n-1)/n<=x/n+(1+n-1)=x/n+1;
摘自《Linux C一站式编程》书中问题
-
整数向上取整
2009-03-11 15:44:00向下取整的运算称为Floor,用数学符号⌊⌋表示,与之相对的,向上取整的运算称为Ceiling,用数学符号⌈⌉表示。C语言定义的取整运算既不是Floor也不是Ceiling,无论操作数是正是负总是把小数部分截断(Truncate),...向下取整的运算称为Floor,用数学符号⌊⌋表示,与之相对的,向上取整的运算称为Ceiling,用数学符号⌈⌉表示。
C语言定义的取整运算既不是Floor也不是Ceiling,无论操作数是正是负总是把小数部分截断(Truncate),所以当操作数为正的时候相当于Floor,当操作符为负的时候相当于Ceiling。
网页分页常用到的一个分页算法
假设变量x和n是两个正整数,我们知道
x/n
这个表达式的结果是取Floor,例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?例如x是17,n是4,则结果是5,而x是16,n是4,则结果是4。#include <stdio.h>
int main()
{
int x,n;
printf("请输入数字:x n/n");
scanf("%d %d",&x,&n);
printf("x/n 向上取整的结果:%d/n",(x+n-1)/n);
printf("x/n 向上取整方法二:%d/n",(int)(((float)x/(float)n)+0.9));
return 0;
} -
二分查找向上还是向下取整_前端经典算法题
2021-02-05 03:51:391: 判断一个字符串是否回文回文是指类似于“上海自来水来自海上”或者“madam”,从前往后和从后往前读,字符串的内容是一样的,称为回文。判断一个字符串是否是回文有很多种思路:1: 创建一个与原字符串前后倒过来...1: 判断一个字符串是否回文
回文是指类似于“上海自来水来自海上”或者“madam”,从前往后和从后往前读,字符串的内容是一样的,称为回文。判断一个字符串是否是回文有很多种思路:
1: 创建一个与原字符串前后倒过来的新字符串,比较二者是否相等,如果相等则是回文
1.1 利用中介Array.reverse()的反转数组的特性
function isPalindRome(str) {
return str.split('').reverse().join('') === str;
}
console.log(isPalindRome('madam')); //true
console.log(isPalindRome('mada')); //false
1.2 不利用任何方法,手动创建新字符串
function isPalindRome(str) {
let newStr = '';
for(let i = str.length - 1; i >= 0; i --){
newStr = newStr + str[i];
}
return newStr === str;
}
console.log(isPalindRome('madam'));
console.log(isPalindRome('mada'));
2: 从字符串的头和尾开始,依次比较字符串组是否相等,逐渐往中间收,如果全部相等,则是回文
function isPalindRome(str) {
let length = str.length;
for(let i = 0; i <= Math.floor(str.length / 2); i ++){
if(str[i] !== str[length - 1 - i]){
return false;
}
}
return true;
}
console.log(isPalindRome('aabbaa')); //true
console.log(isPalindRome('aabaa')); //true
console.log(isPalindRome('abb')); //false
2: 数组去重
2.1 利用ES6新增的Set,因为Set的元素是非重复的
function deduplicate(arr) {
return Array.from(new Set(arr));
}
deduplicate([1,1,2,2,3]);//[1,2,3]
2.1 创建一个新数组,只包含源数组非重复的元素
function deduplicate(arr) {
let newArray = [];
for(let i of arr){
if(newArray.indexOf(i) === -1){
newArray.push(i);
}
}
return newArray;
}
deduplicate([1, 1, 2, 2, 3]);//[1,2,3]
3: 统计字符串中出现最多次数的字符及其次数
function getMaxCount(str) {
let resultMap = new Map();
for (let letter of str) {
if (resultMap.has(letter)) {
resultMap.set(letter, resultMap.get(letter) + 1);
} else {
resultMap.set(letter, 1);
}
}
let maxCount = Math.max(...resultMap.values()); //利用ES6解构,从而可以使用Math.max()
let maxCountLetters = []; //可能几个字符同时都是出现次数最多的,所以用一个Array去装这些字符
resultMap.forEach((value, key, mapSelf) => {
if (value === maxCount) {
maxCountLetters.push(key);
}
});
return {maxCountLetters: maxCountLetters, maxCount: maxCount};
}
getMaxCount('aabbc'); //{maxCountLetters: ['a', 'b'], maxCount: 2}
4: 生成某个整数范围内的随机数
生成随机数,我们需要用到Math.random()这个方法。Math.random()生成0(包含) ~ 1(不包含)之间的小数。
4.1 利用Math.round()进行四舍五入
function randomInt(min, max){
return Math.round(Math.random() * (max - min) + min);
}
randomInt(3, 6),就是 Math.round(Math.random() * 3 + 3);
4.2 利用Math.ceil()向上取整
Math.ceil(num)返回比num大的最小的整数,如果num已经是整数,就返回自己
console.log(Math.ceil(0.95)); //1
console.log(Math.ceil(4)); //4
console.log(Math.ceil(7.0009)); //8
所以,如果我们是要得到3 ~ 6之间的整数,利用ceil()方法就是:
Math.ceil(Math.random()* (6 - 3) + 3)
所以代码实现就是:
function randomRang(min, max) {
return Math.ceil(Math.random()* (max - min) + min);;
}
4.3 利用Math.floor()向下取整
Math.floor()和 Math.ceil()正好相反,Math.floor(num)返回小于num的最大的整数,如果num已经是整数,则返回自己
console.log(Math.floor(0.05)); //0
console.log(Math.floor(4)); //4
console.log(Math.floor(7.95)); //7
如果要得到3 ~ 6之间的整数,利用floor()就是:
Math.floor(Math.random()* (4) + 3);
代码的实现就是:
function randomRang(min, max) {
return Math.floor(Math.random()* (max - min + 1) + min);
}
5: 二分查找
二分查找的前提是有序数组,算法的思想是:
1: 比较需要查找的元素和数组的中间元素做比较,如果相等则返回对应的坐标,否则
2: 如果需要查找的元素比中间元素小,则在数组的前半部分继续采用步骤1的方法查找
3: 如果需要查找的元素比中间元素大,则在数组的后半部分继续采用步骤1的方法查找
4: 递归以上步骤
5: 特别要注意的一点是,如果数组不包含需要查找的元素,则返回-1
function binarySearch(target, arr, startIndex, endIndex) {
let length = arr.length;
if (target < arr[0] || target > arr[length - 1]) {
return -1;
}
let pivotIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
let pivot = arr[pivotIndex];
if (pivot === target) {
return pivotIndex;
} else if (target < pivot) {
return binarySearch(target, arr, startIndex, pivotIndex - 1);
} else {
return binarySearch(target, arr, pivotIndex + 1, endIndex)
}
}
binarySearch(8, [0, 1, 2, 4, 5, 6, 7], 0, 7); //-1
binarySearch(0, [0, 1, 2, 4, 5, 6, 7], 0, 7); //0
6: 使用闭包获取每个li的index
在ES6之前,因为没有块级作用域,在循环体内创建的函数,常常得不到我们想要的结果。例如很经典的依次输出0~9,最后输出9个9;或者如我们这里的获取每个li元素的index:
//fun这种写法,点击每一个li,输出的结果都是5
let fun = function () {
let lists = document.getElementsByTagName('li');
for (var index = 0; index < lists.length; index++) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
}
};
window.onload = fun;
- a
- b
- c
- d
- e
以上的fun的这种写法之所以不对是因为:循环里的每次迭代都共享一个变量index,循环内部创建的函数都保留了对同一个变量的引用,当循环结束的时候,index的值已经变为5,所以点击每一个li都会输出5.
以下的三个函数的实现方式都是对的:
let fun1 = function () {
let lists = document.getElementsByTagName('li');
for (let index in lists) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
}
};
let fun2 = function () {
let lists = document.getElementsByTagName('li');
for (let index = 0; index < lists.length; index++) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
}
};
let fun3 = function () {
let lists = document.getElementsByTagName('li');
for (var index = 0; index < lists.length; index++) {
(function (index) {
lists[index].onclick = function () {
console.log(`index: ${index}`)
}
})(index)
}
};
f1和f2是利用let定义的块级作用域特性,f3是利用闭包的特性。
7: 随机生成指定长度字符串
-
二分查找向上还是向下取整_【算法总结】二分查找续
2021-02-05 03:51:40之前谈的都是查找某个特定值,这里主要是谈论最小化最大值和最大化最小值问题。二分问题最容易搞错的就是终止条件,区间形式,返回lb还是ub或者需不需要再加减一。这里列出了模板一:整型数二分1.最小化最大值问题...之前谈的都是查找某个特定值,这里主要是谈论最小化最大值和最大化最小值问题。二分问题最容易搞错的就是终止条件,区间形式,返回lb还是ub或者需不需要再加减一。这里列出了模板
一:整型数二分
1.最小化最大值问题
形式一:(ub - lb) > 1 区间为 (lb, ub] 结果为 ub
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (C(mid))
ub = mid;
else
lb = mid;
}
// 终止循环时 ub == lb + 1
形式二: (ub - lb) > 0 区间为 [lb, ub] 结果为 ub
while (ub - lb > 0) {
int mid = lb + (ub - lb) / 2;
if (C(mid))
ub = mid;
else
lb = mid + 1;
}
// 终止循环时 ub == lb
2.最大化最小值问题
形式一:(ub - lb) > 1 区间为 [lb, ub) 结果为 lb
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (C(mid))
ub = mid;
else
lb = mid;
}
// 终止循环时 ub == lb + 1
形式二: (ub - lb) > 0 区间为 [lb, ub] 结果为 lb
while (ub - lb > 0) {
int mid = lb + (ub - lb + 1) / 2;
if (C(mid))
lb = mid;
else
ub = mid - 1;
}
// 终止循环时 ub == lb
最小化最大值通过维护ub的位置,最大化最小值通过维护lb的位置。
死循环的核心点在于mid的取值方式:mid = lb + (ub - lb) /2,如果某一时刻 ub == lb + 1,那么由于mid的向下取整,会导致 mid = lb; 假如 if 语句导致 lb = mid 发生,那么就会进入死循环,mid = lb,接着 lb = mid。同样的 mid = lb + (ub - lb + 1) / 2; 如果有 ub = mid操作,也有可能进入死循环。但是ub - lb > 1的终止条件会使得此情况不再发生,原因在于当ub == lb + 1时,由于不满足循环条件循环退出,也就不存在mid = lb或者 mid = ub的操作了。
当区间为闭区间,防止进入死循环的方法就是不能使mid == lb && mid == ub成立
1)最小化最大值 mid 向下取整(维护ub)
如果 if 条件成立,需要维护ub,令ub = mid; 如果不成立则令lb = mid + 1;因为mid向下取整只可能取到lb,为避免死循环就必须使lb = mid + 1;且因为我们要求的是最小化满足条件的值,既然mid不满足循环条件,也就无需考虑此值了。
2)最大化最小值 mid 向上取整(维护lb)
如果 if 条件成立,需要维护b,令lb = mid; 如果不成立则令ub = mid - 1;因为mid向上取整只可能取到ub,为避免死循环就必须使ub = mid - 1;且因为我们要求的是最大化满足条件的值,既然mid不满足循环条件,也就无需考虑此值了。
二:浮点数二分
浮点数二分就通常没有所谓的边界问题了
形式一:
for (int i = 0; i < 100; i++) {
double mid = lb + (ub - lb) / 2;
if (C(mid))
ub = m; // lb = m; according to problem
else
lb = m; // ub = m; according to problem
}
100次的循环精度可达10e-30
形式二:
while (ub - lb > eps) {
double mid = lb + (ub - lb) / 2;
if (C(mid))
ub = m; // lb = m; according to problem
else
lb = m; // lb = m; according to problem
}
eps可根据实际情况来设定,需要注意的是eps如果太小,因为浮点数机器实现的原因,可能会导致死循环。
-
Math中的取整函数
2016-05-07 18:08:57它们函数作用和其英文意义差不多对应,ceil是天花板的意思,该方法就表示向上取整,floor是地板的意思,该方法就表示向下取整,而round有点麻烦,是银行家舍入算法,即四舍六入五取偶。 1、ceil -
算法导论笔记
2017-07-24 17:01:33向上取整和向下取整 模运算 多项式 多项式 对数 阶乘 多重函数 多重对数函数 菲波那切数 线性查找问题 排序 插入排序 归并排序 选择排序 分治策略 最大子数组问题 暴力求解 分治方法 线性非分治方法 矩阵乘法的... -
算法篇:基本运算
2019-11-05 01:14:15基本运算(1) 取整① 向零取整 (小数部分丢弃)② 近似取整(四舍五入)③ 向下取整④ 向上取整(2) 整数除法(3) 浮点数除法(4) 取模运算和求余运算2. 常见运算(1) 求两数中的较大值或较小值(2) 两数交换① 经典三... -
《算法》笔记 8 - 二叉查找树
2019-10-07 22:31:35向上取整、向下取整 选择、排名 范围查找 删除操作 删除最大键、最小键 通用删除操作 二叉查找树 前面了解的无序链表和有序数组在性能方面至少在线性级别,无法用于数据量大的场合。接下来要学习的二叉查找树... -
类欧几里得算法
2020-06-30 00:04:54来源 类欧几里德算法由洪华敦大佬在 2016...⌊ab⌋\left\lfloor\frac{a}{b}\right\rfloor⌊ba⌋ 为 ab\frac{a}{b}ba 向下取整,⌈ab⌉\left\lceil\frac{a}{b}\right\rceil⌈ba⌉ 为 ab\frac{a}{b}ba 向上取整。 -
《算法导论》学习笔记之Chapter9中位数和顺序统计量
2017-12-07 11:33:41第9章 中位数和顺序统计量 先定义:在一个由n个元素组成的集合中,第i个顺序统计量是该...不考虑n的奇偶性,中位数总是出现在i=(n+1)/2向下取整处,也叫下中位数,和i=(n+2)/2向上取整处,也叫上中位数。本书默认下中 -
二叉查找树(算法第四版)
2020-12-03 21:15:44二叉查找树定义与概念基本实现二叉查找树的建立查找插入最大键和最小键向上取整和向下取整选择操作排名删除最大键和删除最小键删除操作范围查找性能分析 定义与概念 一颗二叉查找树(BST)是一颗二叉树,其中每个... -
算法提高 高精度除高精度
2020-06-14 23:40:50资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 给定a, b,求a/b。 输入格式 ... 这里采用ceil() 向上取整 和floor() 向下取整 两个取整函数 这两个函数在math这个头文件里面 */ #include -
uva 10673 - Play with Floor and Ceil(欧几里得算法)
2013-10-21 21:56:56题目大意:给出x 和k,求解p和q使得等式x = p[x / k] + q [ x / k], 两个[x / k]分别为向下取整和向上取整。 解题思路:欧几里得算法求解二元一次方程的解。 #include #include void gcd(long long a, long -
小菜开始学习算法(返璞归真->程序=数据结构+算法)
2012-04-17 20:55:45算法 算法(algorithm)就是定义...RAM模型包含了真实计算机中常见的指令:算术指令(加法,减法,乘法,除法以,取余,向下取整,向上取整指令),数据移动指令(装入,存储,复制指令)和控制指令(条件和非条件转 -
蓝桥杯算法提高 高精度除高精度
2021-02-14 14:18:57题目链接 问题描述 给定a, b,求a/b。 输入格式 输入两行,分别包含...代码1:(采用ceil() 向上取整函数 和floor() 向下取整函数) #include<bits/stdc++.h> using namespace std; int main() { double a, -
【3】数学预备知识
2020-07-22 15:25:12这一讲中主要总结在学习数据结构和算法中所需要的...向上取整和向下取整 对于任意实数x≥0和整数a,b>0 横运算 多项式 指数 对数 阶乘 多重函数 多重对数函数 斐波那契数列 证明方法 鸽巢原理 和式 递推关系 ... -
算法笔记---第二章(C/C++快速入门)
2020-01-05 22:07:00#include <stdio.h> #include <math.h> int main(){ //C语言中提供的实用的数学函数 double db=-12.56; double db2=12.56;... printf("%.2f\n",fabs(db));...用于数值的向下取整和向上取整,返回类型... -
关于负数的除法和余数的结果
2019-10-05 13:25:25之前在算法第四版看过一题,现在编译器试一下余数和被除数同号14 ÷ -3 = -4 ··· 2-14 ÷ -3 = 4 ··· -2-14 ÷ 3 = -4 ··· -2关于商,表达式a/b的商会向0取整,即负数向上取整,正数向下取整,类似于正负数... -
算法导论复习第九章
2013-05-13 16:27:05中位数,包括上中位数(n+1)/2(向上取整),以及(n+1)/2(向下取整),对于n个数中求最大值或者最小值一般情况下的话,需要的是n-1个次比较, 对于求最大也求最小的话,需要比较的次数是2(n-1)次;但是也有一 -
matlab和Verilog之截位,四舍五入和饱和处理
2020-03-27 19:36:31在数字芯片设计中,遇到数据流处理时,经常会遇到饱和,截位和...(1)floor,朝负无穷方向取整,也即向下取整。比如floor(-1.01) =-2;floor(1.9) =1。 (2)ceil,朝正无穷方向取整,也即向上取整。比如ceil(-1.0... -
UVA10673 - Play with Floor and Ceil
2014-05-03 21:34:18思路:分别向上取整和向下取整,然后使用扩展欧几里德算法 #include #include #include #include using namespace std; int x, y, d; void gcd(int a, int b, int &d, int &x, int &y) { if (!b) { d = -
算法导论中文版
2016-10-26 10:13:584.6.2 向下取整和向上取整 思考题 本章注记 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 ?5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 ... -
Java Math的 floor,round和ceil的总结
2011-10-17 13:01:14floor 向下取整 ...round则是4舍5入的计算,round方法,它表示“四舍五入”,算法为Math.floor(x+0.5),即将原来的数字加上0.5后再向下取整,所以,Math.round(11.5)的结果为12,Math.round(-11.5 -
离散数学——数论算法
2015-06-23 13:50:00最近在复习离散数学,这篇文章是《离散数学及其应用》第六版中第三章 算法、整数、和矩阵中涉及到的几个算法,我想了一下,光看... 根据进制转换规则:十进制到n进制整数部分除n取余向上书写,小数部分乘n取整向下... -
常用的数学对象和日期对象
2019-11-30 11:42:18Math.floor() //向下取整 Math.ceil() //向上取整 Math.round() // 四舍五入 Math.random() // 出现 0-1随机小数 Math.max() // 返回最大数 日期对象作用:获取当前时间 date.getFullYear() //年 date.get... -
Java Math的 floor,round和ceil的总结 ,java基础知识
2012-08-18 14:00:13round 则是4舍5入的计算,round方法,它表示“四舍五入”,算法为Math.floor(x+0.5),即将原来的数字加上0.5后再向下取整,所以,Math.round(11.5)的结果为12,Math.round(-11.5)的结果为-11。 Math.floor(1.4)... -
算法导论(原书第三版)
2013-03-06 14:31:344.6.2 向下取整和向上取整 思考题 本章注记 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 球与箱子 5.4.3 ...
-
基于Flink+Hudi构建企业亿级云上实时数据湖教程(PC、移动、小
-
[网鼎杯 2020 青龙组]AreUSerialz
-
西南科技大学《电力电子技术》期末复习题(含答案 精心整理版).pdf
-
零基础极简以太坊智能合约开发环境搭建并开发部署
-
西南科技大学《大学物理B2》两套期末考试试卷(含答案).pdf
-
基于Qt的LibVLC开发教程
-
西南科技大学《自动控制原理》试题库(含答案).pdf
-
刑法学--期末复习题(含答案).pdf
-
西南科技大学《电力工程基础》作业及其答案.pdf
-
浙江科技学院《电力电子》18套历年期末考试试卷.pdf
-
西南科技大学模电试卷及答案.pdf
-
中山大学《俱乐部管理》期末考试试卷.pdf
-
PAT甲级-散列类型-1041 Be Unique解题思路
-
物联网基础篇:快速玩转MQTT
-
编程训练第十九期——跳跃游戏 II
-
刑法--期末复习知识点总结.pdf
-
Mac键盘符号和修饰键说明
-
西南科技大学《软件技术基础》两套期末考试试卷(含答案).pdf
-
朱老师鸿蒙系列课程第1期-3.鸿蒙系统Harmonyos源码配置和管理
-
MySQL 主从复制 Replication 详解(Linux 和 W