輔助分析的工具
這一部分設(shè)置計(jì)數(shù)器采用的是程序設(shè)計(jì)導(dǎo)論2中厘线，二分查找的部分作為例子。
設(shè)置計(jì)數(shù)器
C
#include<stdio.h>
#include<math.h>
int cnt;
int binarysearch(int arr[],int l,int r,int x){
if (l >= r)
cnt += 1 ;
return -1;
int mid = l+r/2;
cnt += 1;
if (arr[mid]==x){
return mid;
cnt += 2;
}
else if(arr[mid] >x){
return binarysearch(arr,l,mid,x);
cnt += 3;
}
else{
return binarysearch(arr,mid,r,x);
cnt += 4;
}
}
int main(){
int n;
int arr[1000];
int x;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&arr[i]);
}
scanf("%d",&x);
printf("%d",binarysearch(arr,0,n,x));
printf("計(jì)數(shù)器指示：%d",cnt);
return 0;
}
C++
#include<iostream>
#include<cmath>
using namespace std;
int cnt;
int binarysearch(int arr[],int l,int r,int x){
if (l >= r)
cnt += 1 ;
return -1;
int mid = l+r/2;
cnt += 1;
if (arr[mid]==x){
return mid;
cnt += 2;
}
else if(arr[mid] >x){
return binarysearch(arr,l,mid,x);
cnt += 3;
}
else{
return binarysearch(arr,mid,r,x);
cnt += 4;
}
}
int main(){
int n;
int arr[1000];
int x;
cin>>n;
for(int i = 0;i<n;i++){
cin>>arr[i];
}
cin>>x;
cout<<binarysearch(arr,0,n,x)<<endl;
cout<<"計(jì)數(shù)器指示："<<cnt<<endl;
return 0;
}
Java
import java.util.Scanner;
class binarysea{
public static int cnt = 0;
public static int binarysearch(int arr[],int l,int r,int x){
if (l >= r){
cnt+=1;
return -1;
}
int mid = l+r/2;
cnt+=1;
if (arr[mid]==x){
cnt+=2;
return mid;
}
else if(arr[mid] >x){
cnt+=3;
return binarysearch(arr,l,mid,x);
}
else{
cnt+=4;
return binarysearch(arr,mid,r,x);
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();5
int arr[] = new int[1000];
for(int i = 0;i<n;i++){
arr[i]=sc.nextInt();
}
int x = sc.nextInt();
System.out.println(binarysearch(arr,0,n,x));
System.out.println("計(jì)數(shù)器指示："+cnt);
}
}
Python
arr = input().split(" ")
x = input()
sorted(arr)
cnt = 0
def binarysearch(arr,l,r,x):
global cnt
if l >= r:
cnt += 1
return -1
mid = int((l + r)/2)
cnt += 1
if arr[mid] == x:
cnt += 2 #將判斷條件的過(guò)程計(jì)算進(jìn)去
return mid
elif arr[mid] > x:
cnt += 3 #將之前判斷的過(guò)程計(jì)算進(jìn)去
return binarysearch(arr,l,mid,x)
else :
cnt += 4 #將之前判斷的過(guò)程計(jì)算進(jìn)去
return binarysearch(arr,mid,r,x)
print(binarysearch(arr,0,len(arr)-1,x))
print("計(jì)數(shù)器指示：{}".format(cnt))
設(shè)置定時(shí)器
這一部分設(shè)置計(jì)數(shù)器采用的是程序設(shè)計(jì)導(dǎo)論2中谒拴，e的近似的部分作為例子臣咖。
C
#include<stdio.h>
#include<math.h>
#include<time.h>
int prod(int n){
int prd = 1;
for(int i = 1; i<= n;i++){
prd = prd * i;
}
return prd;
}
int main(){
int n;
scanf("%d",&n);
double e = 0;
int cnt = 0;
double item = 1;
clock_t start_t,end_t;
start_t = clock();
while(fabs(item)>pow(0.1,n)){
item = 1.0 / prod(cnt);
e = e + item;
cnt = cnt + 1;
}
end_t = clock();
printf("%lf",e);
printf("程序運(yùn)行耗時(shí)：%f\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}
C++
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
int prod(int n){
int prd = 1;
for(int i = 1; i<= n;i++){
prd = prd * i;
}
return prd;
}
int main(){
int n;
cin>>n;
double e = 0;
int cnt = 0;
double item = 1;
clock_t start_t,end_t;
start_t = clock();
while(fabs(item)>pow(0.1,n)){
item = 1.0 / prod(cnt);
e = e + item;
cnt = cnt + 1;
}
end_t = clock();
cout<<e<<endl;
cout<<"程序運(yùn)行耗時(shí)：%f\n"<<(double)(end - start) / CLOCKS_PER_SEC)<<endl;
return 0;
}
Java
import java.util.Scanner;
class eapprox{
public static int prod(int n){
int prd = 1;
for(int i = 1; i<= n;i++){
prd = prd * i;
}
return prd;
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double e = 0;
int cnt = 0;
double item = 1;
long startTime = System.nanoTime();
while(Math.abs(item)>Math.pow(0.1,n)){
item = 1.0 / prod(cnt);
e = e + item;
cnt = cnt + 1;
}
long endTime = System.nanoTime();
long usedTime = endTime-startTime;
System.out.println(e);
System.out.println(usedTime+"ms");
}
}
Python
import time
n = int(input())
e = 0
cnt = 0
item = 1
def prod(n):
prd = 1.0
for i in range(1,n+1):
prd = prd * i
return prd
start_time = time.process_time()#程序開(kāi)始
while abs(item) > pow(0.1,n):
item = 1.0 /prod(cnt)
e = e + item
cnt = cnt +1
end_time = time.process_time()#程序結(jié)束
print(e)
print("計(jì)數(shù)器指示：{}".format(end_time-start_time))
設(shè)置進(jìn)程資源檢測(cè)
略
大數(shù)四則運(yùn)算
加法
C
#include<string.h>
#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
char a[1000000];
char b[1000000];
char c[1000001];
void add(char a[],char b[]){
strrev(a);
strrev(b);
int tem = 0;
int cnt = 0;
int len_a = strlen(a);
int len_b = strlen(b);
int item = 0;
for(int i = 0 ; i < min(len_a,len_b);i++){
item = a[i]-'0'+b[i]-'0'+tem;
if (item>10){
tem = 1;
item %= 10;
}
else{
tem = 0;
}
c[cnt++]=item+'0';
}
if(len_a>len_b){
for(int i = len_b;i<len_a;i++){
item = a[i]-'0'+tem;
if(item >= 10){
tem = 1;
item %= 10;
}
else{
tem = 0;
}
c[cnt++]=item+'0';
}
}
if(len_b>len_a){
for(int i = len_a;i<len_b;i++){
item = a[i]-'0'+tem;
if(item >= 10){
tem = 1;
item %= 10;
}
else{
tem = 0;
}
c[cnt++]=item+'0';
}
}
if (tem != 0){
c[cnt++]=tem+'0';
}
strrev(c);
}
int main(){
scanf("%s %s",&a,&b);
add(a,b);
printf(c);
return 0;
}
C++
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
char a[1000000];
char b[1000000];
char c[1000001];
void add(char a[],char b[]){
strrev(a);
strrev(b);
int tem = 0;
int cnt = 0;
int len_a = strlen(a);
int len_b = strlen(b);
int item = 0;
for(int i = 0 ; i < min(len_a,len_b);i++){
item = a[i]-'0'+b[i]-'0'+tem;
if (item>10){
tem = 1;
item %= 10;
}
else{
tem = 0;
}
c[cnt++]=item+'0';
}
if(len_a>len_b){
for(int i = len_b;i<len_a;i++){
item = a[i]-'0'+tem;
if(item >= 10){
tem = 1;
item %= 10;
}
else{
tem = 0;
}
c[cnt++]=item+'0';
}
}
if(len_b>len_a){
for(int i = len_a;i<len_b;i++){
item = a[i]-'0'+tem;
if(item >= 10){
tem = 1;
item %= 10;
}
else{
tem = 0;
}
c[cnt++]=item+'0';
}
}
if (tem != 0){
c[cnt++]=tem+'0';
}
strrev(c);
}
int main(){
cin>>a>>b;
add(a,b);
cout<<c<<endl;
return 0;
}
Java
Python
def add(a,b):
a = a[::-1]
b = b[::-1]
c = []
tem = 0
for x,y in zip(a,b):
item = int(x)+int(y)+tem
if item >= 10:
tem = 1
item %= 10
else:
tem = 0
c.append(str(item))
if len(a) > len(b):
for i in range(len(b),len(a)):
item = int(a[i])+tem
if item >= 10:
tem = 1
item %= 10
else:
tem = 0
c.append(str(item))
if len(a) < len(b):
for i in range(len(a),len(b)):
item = int(b[i])+tem
if item >= 10:
tem = 1
item %= 10
else:
tem = 0
c.append(str(item))
if tem != 0:
c.append(str(tem))
c = "".join(c)
return c[::-1]
a,b = input().split(" ")
print(add(a,b))
減法
C
#include<string.h>
#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
char a[1000000];
char b[1000000];
char c[1000001];
void sub(char a[],char b[]){
strrev(a);
strrev(b);
int tem = 0;
int cnt = 0;
int len_a = strlen(a);
int len_b = strlen(b);
int item = 0;
for(int i = 0; i < min(len_a,len_b);i++){
if(a[i]+tem>=b[i]){
item = a[i]-'0'+tem-(b[i]-'0');
tem = 0;
}
else{
item = a[i]-'0'+10+tem-(b[i]-'0');
tem = -1;
}
c[cnt++]=item+'0';
}
if(len_a>len_b){
for(int i = len_b;i<len_a;i++){
item = a[i]-'0'+tem;
if(item<0){
tem = -1;
item += 10;
}
else{
tem = 0;
}
c[cnt++] = item+'0';
}
}
strrev(c);
}
int main(){
scanf("%s %s",&a,&b);
sub(a,b);
printf(c);
return 0;
}
C++
#include<string.h>
#include<iostream>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
char a[1000000];
char b[1000000];
char c[1000001];
void sub(char a[],char b[]){
strrev(a);
strrev(b);
int tem = 0;
int cnt = 0;
int len_a = strlen(a);
int len_b = strlen(b);
int item = 0;
for(int i = 0; i < min(len_a,len_b);i++){
if(a[i]+tem>=b[i]){
item = a[i]-'0'+tem-(b[i]-'0');
tem = 0;
}
else{
item = a[i]-'0'+10+tem-(b[i]-'0');
tem = -1;
}
c[cnt++]=item+'0';
}
if(len_a>len_b){
for(int i = len_b;i<len_a;i++){
item = a[i]-'0'+tem;
if(item<0){
tem = -1;
item += 10;
}
else{
tem = 0;
}
c[cnt++] = item+'0';
}
}
strrev(c);
}
int main(){
cin>>a>>b;
sub(a,b);
cout<<c<<endl;
return 0;
}
Java
Python
def sub(a,b):
a = a[::-1]
b = b[::-1]
c = []
tem = 0
for x,y in zip(a,b):
if int(x)+tem >= int(y):
item = int(x)+tem-int(y)
tem = 0
else:
item = int(x)+tem+10-int(y)
tem = -1
c.append(str(item))
if len(a) > len(b):
for i in range(len(b),len(a)):
item = int(a[i])+tem
if item < 0:
tem = -1
item += 10
else:
tem = 0
c.append(str(item))
c = "".join(c)
return c[::-1]
a,b = input().split(" ")
print(sub(a,b))
乘法
略
除法
略
素?cái)?shù)篩
暴力算法
C
#include<stdio.h>
#include<math.h>
int a[10000000];
int violet_sieve_core(int num){
if (num<=1){
return 0;
}
for(int i = 2;i < num;i++){
if(num%i == 0){
return 0;
}
}
return 1;
}
int cnt;
void violet_sieve(int n){
for(int i = 2;i < n+1;i++){
if(violet_sieve_core(i)){
a[cnt++]=i;
}
}
}
int main(){
int n;
scanf("%d",&n);
violet_sieve(n);
for(int i = 0 ;i<cnt;i++){
printf("%d ",a[i]);
}
return 0;
}
C++
#include<iostream>
#include<cmath>
int a[10000000];
int violet_sieve_core(int num){
if (num<=1){
return 0;
}
for(int i = 2;i < num;i++){
if(num%i == 0){
return 0;
}
}
return 1;
}
int cnt;
void violet_sieve(int n){
for(int i = 2;i < n+1;i++){
if(violet_sieve_core(i)){
a[cnt++]=i;
}
}
}
int main(){
int n;
cin>>n;
violet_sieve(n);
for(int i = 0 ;i<cnt;i++){
cout<<a[i]<<endl;
}
return 0;
}
Java
Python
def violet_sieve(num):
if num < 2:
return False
for i in range(2,num):
if num % i == 0:
return False
return True
n = int(input())
for i in range(2,n+1):
if violet_sieve(i):
print(i)
埃篩
C
#include<stdio.h>
#include<math.h>
int a[10000000];
int cnt;
int p[100000000];
void eratos_sieve(int n){
for(int i = 2;i<n;i++){
for(int j = 2; i *j <= n;j++){
p[i*j] = 0;
}
if(!p[i]){
a[cnt++]=i;
}
}
}
int main(){
int n;
scanf("%d",&n);
eratos_sieve(n);
for(int i = 0 ;i<cnt;i++){
printf("%d ",a[i]);
}
return 0;
}
C++
#include<iostream>
#include<cmath>
int a[10000000];
int cnt;
int p[100000000];
void eratos_sieve(int n){
for(int i = 2;i<n;i++){
for(int j = 2; i *j <= n;j++){
p[i*j] = 0;
}
if(!p[i]){
a[cnt++]=i;
}
}
}
int main(){
int n;
cin>>n;
eratos_sieve(n);
for(int i = 0 ;i<cnt;i++){
cout<<a[i]<<endl;
}
return 0;
}
Java
Python
def eratos_sieve(n):
primes = [True] * (n+1)
p = 2
while p*p <= n:
if primes[p]:
for i in range(p*2,n+1,p):
primes[i] = False
p += 1
primes = [element for element in range(2,n) if primes[element]]
return primes
n = int(input())
for i in eratos_sieve(n):
print(i)
歐拉篩
C
#include<stdio.h>
#include<math.h>
int a[10000000];
int cnt;
int p[100000000];
void euler_sieve(int n){
for(int i = 2;i<n;i++){
if(!p[i]){
a[cnt++]=i;
}
for(int j = 0; j<cnt &&i *a[j] <= n;j++){
p[i*a[j]]= 1;
if(i % a[j] == 0) break;
}
}
}
int main(){
int n;
scanf("%d",&n);
euler_sieve(n);
for(int i = 0 ;i<cnt;i++){
printf("%d ",a[i]);
}
return 0;
}
C++
#include<iostream>
#include<cmath>
using namespace std;
int a[10000000];
int cnt;
int p[100000000];
void euler_sieve(int n){
for(int i = 2;i<n;i++){
if(!p[i]){
a[cnt++]=i;
}
for(int j = 0; j<cnt &&i *a[j] <= n;j++){
p[i*a[j]]= 1;
if(i % a[j] == 0) break;
}
}
}
int main(){
int n;
cin>>n;
euler_sieve(n);
for(int i = 0 ;i<cnt;i++){
cin>>a[i]<<endl;
}
return 0;
}
Java
Python
def euler_sieve(n):
cnt = 0
flag = [True] * (n+1)
primes = []
for i in range(2,n):
if flag[i]:
primes.append(i)
cnt += 1
j = 0
while j < cnt and i * prime[j] < n:
flag[i*prime[j]] = False
if i%prime[j] == 0:
break
j += 1
return primes
n = int(input())
for i in euler_sieve(n):
print(i)
求最大公約數(shù)
輾轉(zhuǎn)相除法
C
#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
int gcd(int a,int b){
int a_ = max(a,b);
int b_ = min(a,b);
return b==0?a:gcd(b,a%b);
}
int main(){
int m,n;
scanf("%d %d",&m,&n);
printf("%d",gcd(m,n));
return 0;
}
C++
#include<iostream>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int gcd(int a,int b){
int a_ = max(a,b);
int b_ = min(a,b);
return b==0?a:gcd(b,a%b);
}
int main(){
int m,n;
cin>>m>>n;
cout<<gcd(m,n)<<endl;
return 0;
}
Java
Python
def gcd(a,b):
a,b = max(a,b),min(a,b)
if b == 0:
return a
else:
return gcd(b,a%b)
m,n = [int(i) for i in input().split()]
print(gcd(m,n))
stein算法
C
#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
int stein(int m,int n){
int a = max(m,n);
int b = min(m,n);
if(b == 0){
return a;
}
if(a%2==0 && b%2==0){
return stein(a>>1,b>>1)<<1;
}
if(a%2==0){
return stein(a>>1,b);
}
if(b%2==0){
return stein(a,b>>1);
}
return stein((a+b)>>1,(a-b)>>1);
}
int main(){
int m,n;
scanf("%d %d",&m,&n);
printf("%d",stein(m,n));
return 0;
}
C++
#include<iostream>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int stein(int m,int n){
int a = max(m,n);
int b = min(m,n);
if(b == 0){
return a;
}
if(a%2==0 && b%2==0){
return stein(a>>1,b>>1)<<1;
}
if(a%2==0){
return stein(a>>1,b);
}
if(b%2==0){
return stein(a,b>>1);
}
return stein((a+b)>>1,(a-b)>>1);
}
int main(){
int m,n;
cin>>m>>n;
cout<<stein(m,n)<<endl;
return 0;
}
Java
Python
def stein(a,b):
a,b = max(a,b),min(a,b)
if b == 0:
return a
if a % 2 == 0 and b % 2 == 0:
return stein(a>>1,b>>1)<<1
if a % 2 == 0:
return stein(a>>1,b)
if b % 2 == 0:
return stein(a,b>>1)
return stein((a+b)>>1,(a-b)>>1)
m,n = [int(i) for i in input().split()]
print(stein(m,n))
排序算法
插入排序
C
#include<stdio.h>
void insert_sort(int arr[], int len){
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
int main(){
int n;
int arr[100000];
scanf("%d",&n);
for(int i = 0 ;i < n;i++){
scanf("%d",&arr[i]);
}
insert_sort(arr,n);
for(int i = 0 ;i < n;i++){
printf("%d ",arr[i]);
}
}
C++
#include<iostream>
using namespace std;
void insert_sort(int arr[], int len){
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
int main(){
int n;
int arr[100000];
scanf("%d",&n);
for(int i = 0 ;i < n;i++){
scanf("%d",&arr[i]);
}
insert_sort(arr,n);
for(int i = 0 ;i < n;i++){
printf("%d ",arr[i]);
}
}
Java
Python
def insertsort(arr):
n = len(arr)
for i in range(1,n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1]=arr[j]
j -= 1
arr[j+1] = key
arr = [int(i)for i in input().split(" ")]
insertsort(arr)
print(arr)
快速排序
C
#include<stdio.h>
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else{
left++;
swap(&arr[left], &arr[end]);
}
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main(){
int n;
int arr[100000];
scanf("%d",&n);
for(int i = 0 ;i < n;i++){
scanf("%d",&arr[i]);
}
quick_sort(arr,n);
for(int i = 0 ;i < n;i++){
printf("%d ",arr[i]);
}
}
C++
#include<iostream>
using namespace std;
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else{
left++;
swap(&arr[left], &arr[end]);
}
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main(){
int n;
int arr[100000];
cin>>n;
for(int i = 0 ;i < n;i++){
cin>>arr[i];
}
quick_sort(arr,n);
for(int i = 0 ;i < n;i++){
cin>>arr[i];
}
}
Java
Python
def quick_sort(arr, first, last):
if first >= last:
return
mid = arr[first]
low = first
high = last
while low < high:
while low < high and arr[high] >= mid:
high -= 1
arr[low] = arr[high]
while low < high and arr[low] < mid:
low += 1
arr[high] = arr[low]
arr[low] = mid
quick_sort(arr, first, low-1)
quick_sort(arr, low+1, last)
arr = [int(i)for i in input().split(" ")]
quick_sort(arr,0,len(arr)-1)
print(arr)
