中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

wordpress頁面屬性模板怎么添加泰安網(wǎng)站推廣優(yōu)化

wordpress頁面屬性模板怎么添加,泰安網(wǎng)站推廣優(yōu)化,網(wǎng)頁設(shè)計(jì)與網(wǎng)頁制作,做網(wǎng)站的圖片=gif整數(shù)二分算法和浮點(diǎn)數(shù)二分算法 二分 現(xiàn)實(shí)中運(yùn)用到二分的就是猜數(shù)字的游戲 假如有A同學(xué)說B同學(xué)所說數(shù)的大小,B同學(xué)要在1~100中間猜中數(shù)字65,當(dāng)B同學(xué)每次說的數(shù)都是范圍的一半時(shí)這就算是一個(gè)二分查找的過程 二分查找的前提是這個(gè)數(shù)字序列要有單調(diào)性 基…

整數(shù)二分算法和浮點(diǎn)數(shù)二分算法


二分

現(xiàn)實(shí)中運(yùn)用到二分的就是猜數(shù)字的游戲 假如有A同學(xué)說B同學(xué)所說數(shù)的大小,B同學(xué)要在1~100中間猜中數(shù)字65,當(dāng)B同學(xué)每次說的數(shù)都是范圍的一半時(shí)這就算是一個(gè)二分查找的過程
在這里插入圖片描述

二分查找的前提是這個(gè)數(shù)字序列要有單調(diào)性

基本步驟

初始化:

設(shè)定兩個(gè)指針,left 和 right,分別指向數(shù)組的起始和末尾。

計(jì)算中間位置:

使用公式 mid = left + (right - left) / 2 或者left+right>>1計(jì)算中間位置。

比較:

如果中間位置的元素等于目標(biāo)值,返回中間位置。
如果目標(biāo)值小于中間位置的元素,則將 right 更新為 mid - 1,繼續(xù)在左半部分查找。
如果目標(biāo)值大于中間位置的元素,則將 left 更新為 mid + 1,繼續(xù)在右半部分查找。

重復(fù):

重復(fù)步驟 2 和 3,直到 left 超過 right。

結(jié)束:

如果在查找過程中未找到目標(biāo)值,返回一個(gè)表示未找到的結(jié)果(如 -1 或 None)。

二分查找算法的時(shí)間復(fù)雜度是 O(log n),非常高效。

整數(shù)二分

二分的本質(zhì)并不是一定要單調(diào),而是對一個(gè)區(qū)間可以化分成兩個(gè)部分,一部分一定滿足條件,另一部分一定不滿足,對于滿足這種條件的我們可以找出兩個(gè)邊界點(diǎn),這樣的話二分算法可以尋找這個(gè)性質(zhì)的邊界(紅色和黑色的邊界都行,因?yàn)槭钦麛?shù)二分所以兩邊界不重合)。
在這里插入圖片描述

第一種情況(二分左半部分)

假如說有一串?dāng)?shù)字1,2,3,3,4,4,5,6,8,8我們需要找到滿足小于等于3的最大情況的子序列,也就是我們需要找到最后一次出現(xiàn)的3,我們可以如何做呢?
我們讓一個(gè)mid=(l+r+1)/2 假如說a[mid]<=3,此時(shí)if(check(mid))==true說明此時(shí)mid指向的值可能是答案,但是我們無法保證其后面還有沒有答案是<=3的,所以此時(shí)應(yīng)該是l=mid,假如說此時(shí)a[mid]>=3,if(check(mid))==false說明此時(shí)mid指向的是一定不滿足條件的的那么此時(shí)應(yīng)該是r=mid-1。
在這里插入圖片描述
我們繼續(xù)不段重復(fù)以上操作直到l>=r時(shí)退出循環(huán)。

第二種情況(二分右半部分)

還是這個(gè)數(shù)字序列這次我們要找1,2,3,3,4,4,5,6,8,8中第一次出現(xiàn)3的位置,我們應(yīng)該怎么做呢?
我們還是讓一個(gè)mid=(l+r)/2 假如說a[mid]>=3,此時(shí)if(check(mid))==true說明此時(shí)mid指向的值可能是答案,但是我們無法保證其前面還有沒有答案是>=3的,所以此時(shí)應(yīng)該是r=mid,假如說此時(shí)a[mid]<=3,if(check(mid))==false說明此時(shí)mid指向的是一定不滿足條件的的那么此時(shí)應(yīng)該是l=mid+1

注意:第一種情況是(l+r+1)而不是(l+r)為為什么呢?

因?yàn)橛?jì)算機(jī)的除法都是向下取整的所以就會出現(xiàn)問題,假如說此時(shí)l=r-1那么mid=(l+r)/2=(l+l+1)/2=l然后我們假如發(fā)現(xiàn)l還是滿足條件的,那么此時(shí)就會陷入l=mid,mid=l的死循環(huán)

我們來寫一道題

洛谷P2249
下面的代碼是既有第一次出現(xiàn),也有最后一次出現(xiàn)的,兩種情況都寫了。
代碼如下:

#include <iostream>
using namespace std;const int N = 1e5 + 10; // 定義數(shù)組的最大容量,數(shù)組a最多可以存放1e5個(gè)元素
int a[N], n, m; // 定義全局變量數(shù)組a,n為數(shù)組長度,m為查詢次數(shù)// check1函數(shù)用于檢查a[mid]是否大于等于目標(biāo)值x
bool check1(int mid, int x) {if (a[mid] >= x) {return true; // 如果a[mid]大于等于x,返回true,表示滿足條件} else {return false; // 否則返回false,表示不滿足條件}
}// check2函數(shù)用于檢查a[mid]是否小于等于目標(biāo)值x
bool check2(int mid, int x) {if (a[mid] <= x) {return true; // 如果a[mid]小于等于x,返回true,表示滿足條件} else {return false; // 否則返回false,表示不滿足條件}
}int main() {cin >> n >> m; // 輸入數(shù)組的長度n和查詢的次數(shù)mfor (int i = 1; i <= n; i++) {cin >> a[i]; // 依次輸入數(shù)組a的元素}while (m--) { // 對每一次查詢進(jìn)行處理,m次查詢int x; // 定義要查詢的目標(biāo)值xcin >> x; // 輸入目標(biāo)值x// 首先進(jìn)行二分查找,尋找第一個(gè)大于等于x的位置int l = 1, r = n; // 初始化左右邊界,l是左邊界,r是右邊界while (l < r) { // 當(dāng)左邊界小于右邊界時(shí),繼續(xù)二分查找int mid = (l + r) >> 1; // 計(jì)算中間位置midif (check1(mid, x)) { // 如果a[mid]大于等于xr = mid; // 縮小右邊界至mid} else {l = mid + 1; // 否則縮小左邊界至mid+1}}// 查找完成后,檢查a[l]是否等于目標(biāo)值xif (a[l] == x) {cout << l << " "; // 如果a[l]等于x,輸出位置l} else {cout << -1 << " "; // 如果a[l]不等于x,輸出-1表示未找到}// 再進(jìn)行一次二分查找,尋找最后一個(gè)小于等于x的位置l = 1, r = n; // 重新初始化左右邊界while (l < r) {int mid = (l + r + 1) >> 1; // 計(jì)算中間位置mid,向上取整if (check2(mid, x)) { // 如果a[mid]小于等于xl = mid; // 縮小左邊界至mid} else {r = mid - 1; // 否則縮小右邊界至mid-1}}// 查找完成后,再次檢查a[l]是否等于目標(biāo)值xif (a[l] == x) {cout << l << " "; // 如果a[l]等于x,輸出找到的最后位置l} else {cout << -1 << " "; // 如果沒找到,輸出-1}cout<<endl;}
}

整數(shù)二分模板

bool check(int x) {// 這里是判斷x是否滿足某種性質(zhì)的函數(shù),具體實(shí)現(xiàn)取決于實(shí)際問題// 可以根據(jù)x的值來返回true或false,用于二分查找中的判斷/* ... */
}// 區(qū)間[l, r]被劃分為[l, mid]和[mid + 1, r]時(shí)使用的二分查找
int bsearch_1(int l, int r) {// 二分查找的目的是在區(qū)間[l, r]中尋找滿足某種性質(zhì)的最小位置// l 是左邊界,r 是右邊界,最終返回滿足性質(zhì)的最小下標(biāo)while (l < r) { // 當(dāng)左邊界小于右邊界時(shí),繼續(xù)進(jìn)行二分查找int mid = (l + r) >> 1; // 計(jì)算中間位置mid,使用右移操作進(jìn)行快速計(jì)算,相當(dāng)于 (l + r) / 2if (check(mid)) { // 如果check(mid)為true,表示mid滿足性質(zhì)r = mid; // 將右邊界縮小到mid,因?yàn)槲覀円覞M足性質(zhì)的最小位置} else { // 否則,mid不滿足性質(zhì)l = mid + 1; // 將左邊界縮小到mid + 1,因?yàn)閙id以及它左邊的值都不滿足條件}}return l; // 返回最終的左邊界,此時(shí)l == r,且為滿足性質(zhì)的最小位置
}// 區(qū)間[l, r]被劃分為[l, mid - 1]和[mid, r]時(shí)使用的二分查找
int bsearch_2(int l, int r) {// 二分查找的目的是在區(qū)間[l, r]中尋找滿足某種性質(zhì)的最大位置// l 是左邊界,r 是右邊界,最終返回滿足性質(zhì)的最大下標(biāo)while (l < r) { // 當(dāng)左邊界小于右邊界時(shí),繼續(xù)進(jìn)行二分查找int mid = (l + r + 1) >> 1; // 計(jì)算中間位置mid,并向上取整,確保mid偏向右側(cè)if (check(mid)) { // 如果check(mid)為true,表示mid滿足性質(zhì)l = mid; // 將左邊界縮小到mid,因?yàn)槲覀円覞M足性質(zhì)的最大位置} else { // 否則,mid不滿足性質(zhì)r = mid - 1; // 將右邊界縮小到mid - 1,因?yàn)閙id以及它右邊的值都不滿足條件}}return l; // 返回最終的左邊界,此時(shí)l == r,且為滿足性質(zhì)的最大位置
}

浮點(diǎn)數(shù)二分算法

浮點(diǎn)數(shù)二分相較于整數(shù)二分更加簡單因?yàn)橹挥幸粋€(gè)模板,并且沒有邊界問題,浮點(diǎn)數(shù)的二分查找可以用于求解需要精確值的問題,例如求方程的解或幾何問題中涉及浮點(diǎn)精度的求解。與整數(shù)二分查找不同,浮點(diǎn)數(shù)二分查找必須考慮精度問題,因?yàn)楦↑c(diǎn)數(shù)無法精確到某個(gè)具體值,所以我們需要一個(gè)精度(如 epsilon),用于判斷二分查找的終止條件。

假如說我們需要找一個(gè)數(shù)x的平方等于目標(biāo)值2

代碼如下:

#include <iostream>
#include <cmath> // 包含abs函數(shù),用于計(jì)算絕對值
using namespace std;// 定義一個(gè)需要使用二分法求解的函數(shù),返回值為目標(biāo)函數(shù)值
double f(double x) {// 舉例:尋找函數(shù) f(x) = x^2 - 2 的根return x * x - 2;
}int main() {double l = 0, r = 2; // 初始區(qū)間[l, r],假設(shè)根位于[0, 2]之間double eps = 1e-7;   // 定義精度eps,即當(dāng)結(jié)果誤差小于1e-7時(shí)停止迭代// 當(dāng)區(qū)間寬度大于精度要求時(shí),繼續(xù)二分while (r - l > eps) {double mid = (l + r) / 2; // 計(jì)算中間值if (f(mid) > 0) { // 如果 f(mid) > 0,表示 mid 處的值在根的右側(cè)r = mid; // 縮小右邊界至mid} else { // 否則 f(mid) <= 0,表示 mid 處的值在根的左側(cè)或是根l = mid; // 縮小左邊界至mid}}// 輸出結(jié)果,l 和 r 最終都會逼近根cout << "x ≈ " << l << endl;cout << "驗(yàn)證結(jié)果: f(x) = " << f(l) << endl; // 輸出驗(yàn)證f(l)接近0
}

浮點(diǎn)數(shù)二分模板

// 函數(shù)原型:在浮點(diǎn)數(shù)區(qū)間 [l, r] 上使用二分查找,找到滿足某種性質(zhì)的浮點(diǎn)數(shù)
double bsearch_3(double l, double r)
{const double eps = 1e-6;   // eps 是精度控制的參數(shù),當(dāng)區(qū)間長度小于 eps 時(shí)停止二分查找// 1e-6 表示小數(shù)點(diǎn)后 6 位精度,可根據(jù)題目要求調(diào)整精度// 當(dāng)區(qū)間長度大于 eps 時(shí),繼續(xù)進(jìn)行二分查找while (r - l > eps){// 計(jì)算區(qū)間的中點(diǎn) middouble mid = (l + r) / 2;// 調(diào)用 check 函數(shù)判斷 mid 是否滿足給定的性質(zhì)// 假設(shè) check(mid) 返回 true,則意味著 mid 及其右側(cè)可能滿足性質(zhì),// 因此將右區(qū)間收縮到 mid,繼續(xù)在左側(cè)區(qū)間 [l, mid] 上搜索if (check(mid)) r = mid;// 否則,mid 及其左側(cè)不滿足性質(zhì),因此我們將左區(qū)間收縮到 mid,繼續(xù)在右側(cè)區(qū)間 [mid, r] 上搜索else l = mid;}// 最后返回左邊界 l(或右邊界 r),此時(shí)區(qū)間已經(jīng)很小,接近于精度要求的結(jié)果// 因?yàn)?l 和 r 的距離非常小,最終答案應(yīng)為 l 或 r 的近似值return l;
}

整數(shù)二分算法和浮點(diǎn)數(shù)二分算法源代碼

http://www.risenshineclean.com/news/53698.html

相關(guān)文章:

  • 上海網(wǎng)站建設(shè)技術(shù)托管軟文臺
  • 政府網(wǎng)站開發(fā)周期自己做一個(gè)網(wǎng)站
  • 網(wǎng)站運(yùn)營流程18款免費(fèi)軟件app下載
  • 杭州網(wǎng)站設(shè)計(jì)詢問藍(lán)韻網(wǎng)絡(luò)跟我學(xué)seo
  • idea網(wǎng)站開發(fā)上海網(wǎng)站建設(shè)開發(fā)
  • 做it的在哪個(gè)網(wǎng)站找工作百度注冊公司網(wǎng)站
  • android做網(wǎng)站網(wǎng)站怎么做
  • 做網(wǎng)站重慶今天的病毒感染情況
  • 域名設(shè)計(jì)與分析沈陽seo排名優(yōu)化推廣
  • 設(shè)計(jì)需要看的網(wǎng)站有哪些seo英文怎么讀
  • 自己做的網(wǎng)站如何被百度檢索優(yōu)秀的軟文廣告案例
  • 網(wǎng)站建設(shè)優(yōu)化服務(wù)好么搜狗站長平臺驗(yàn)證網(wǎng)站
  • 太原網(wǎng)站制作電話百度搜索排行
  • 全球最好的設(shè)計(jì)網(wǎng)站怎么找拉新推廣平臺
  • 網(wǎng)站建設(shè)公司公司好免費(fèi)b2b推廣網(wǎng)站大全
  • 網(wǎng)站建設(shè)軟件下載西安seo服務(wù)公司
  • 網(wǎng)站的字體做多大合適如何推廣自己的產(chǎn)品
  • 建站公司maxsem競價(jià)托管多少錢
  • 網(wǎng)站開發(fā)人月薪網(wǎng)絡(luò)營銷方法有哪幾種
  • 做現(xiàn)貨IC電子網(wǎng)站的惠州seo計(jì)費(fèi)管理
  • 做網(wǎng)站有地域限制嗎專業(yè)seo站長工具
  • 二級域名子域名大全領(lǐng)碩網(wǎng)站seo優(yōu)化
  • 淘寶網(wǎng)作圖做網(wǎng)站網(wǎng)站托管代運(yùn)營
  • wordpress買域名百度搜索排名優(yōu)化哪家好
  • 如何注銷網(wǎng)站備案號數(shù)據(jù)分析培訓(xùn)班
  • 網(wǎng)站的運(yùn)營管理方案長沙seo結(jié)算
  • seo如何根據(jù)網(wǎng)站數(shù)據(jù)做報(bào)表怎么找專業(yè)的營銷團(tuán)隊(duì)
  • 如何做轉(zhuǎn)運(yùn)網(wǎng)站引流推廣犯法嗎
  • wordpress添加版權(quán)信息如何進(jìn)行網(wǎng)站性能優(yōu)化
  • 怎么做直播網(wǎng)站超管做網(wǎng)絡(luò)推廣的團(tuán)隊(duì)