day1

day1 - 初窥门径

---

为什么要学编程

人工智能，边缘计算，大数据，通信工程，互联网，计算机科学与技术。。。

1. chatGPT
2. stablediffusion
3. VITS
4. AR/VR
5. 游戏制作

算法入门

神经网络，数据挖掘，数字孪生，进化算法，目标检测，语义分割。。。

1. 什么是算法
2. 程序=数据结构+算法
3. 怎么学算法

---

分治

1. 二分查找(非递归)

   #include <bits/stdc++.h> 
   using namespace std;
   int a[1000000] = {0};//太大的数组要放到全局变量去
   int main(){
       int n,x,r; 
       int i,j,mid,left,right; 
       cin>>n;
       //读入数组元素
       for(i = 0;i < n;i++){ 
           cin>>a[i];
       }
       cin>>x;
       left = 0;
       right = n - 1;
       r = -1;//假设没找到
       //当还有求解范围时
       while(left <= right){
           //中间下标
           mid = (left + right) / 2;
           if(a[mid] == x) {
               r = mid;
               break;
           }else 
           if(x < a[mid]){
               right = mid - 1;
           }else 
           if(x > a[mid]){ 
               left = mid + 1;
           }
       }
       //输出位置 
       cout<<(r == -1?-1:r+1)<<endl;
       return 0;
   }

2. 二分查找(递归)

   #include <bits/stdc++.h> 
   using namespace std;
   int a[1000000],x;
   //求岀数组中x的下标
   int fun(int left,int right){
       //递归岀口
       if(left <= right){
           int mid = (left + right) / 2;
           //如果在前一半
           if(x < a[mid]){ 
               return fun(left,mid-1);
           } else 
           if(x > a[mid]){
                return fun(mid+1,right);
           }else{ 
               return mid;
           }
       }else{
           return -1;
       }
   }
   int main(){
       int n;
       cin>>n;
       //读入凝组元素
       for(i = 0;i < n;i++){
           cin>>a[i];
       }
       cin>>x;
       //输出位置 
       int r = fun(0,n-1);
       cout<<(r == -1?-1:r+1)<<endl;
       return 0;
   }

3. 思考题

洛谷 P1024

一元三次方程求解

1. 零点存在定理，f(x1)*f(x2)<0
2. 考虑误差esp

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define eps 1e-4
double a,b,c,d;
double f(double x){
	return a*x*x*x+b*x*x+c*x+d;
}
int main(){
	double y;
	cin>>a>>b>>c>>d;
	for(int i=-100;i<=100;i++){
		if(fabs(f(i*1.0))<eps){
			printf("%.2lf ",i*1.0);
			continue;
		}
		if(fabs(f((i+1)*1.0))<eps)
			continue;
		if(f(i)*f(i+1)<0){
			double l=i*1.0,r=(i+1)*1.0,mid;
			while(r-l>eps){
				mid=(l+r)/2;
				if(f(l)*f(mid)<0) r=mid;
				if(f(mid)*f(r)<0) l=mid;
				if(f(mid)==0) break;
			}
			printf("%.2lf ",mid);
		}
    }
	return 0;
}