系列文章目录
文章目录
- 系列文章目录
- 前言
- 一、题目
-
- 1、在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。
- 2.给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.
- 3、给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。
- 结尾
前言
随着计算机编程语言的发展，很多东西逐渐饱和了；但是算法会跟随你一辈子的逻辑思维，任何人都拿不走.
提示：以下是本篇文章正文内容，下面案例可供参考
一、题目
1、在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。
答案:
请输入纸张名称 (A0, A1, A2, ..., A9): A6
A6: 105 mm × 148 mm
代码:
#include <stdio.h>
#include <string.h>
struct Paper {
int width; // 宽度 (mm)
int height; // 高度 (mm)
};
// 初始化 ISO A 系列纸张尺寸
void initializePapers(struct Paper papers[]) {
papers[0].width = 841; // A0
papers[0].height = 1189;
int i;
for ( i = 1; i <= 9; i++) {
papers[i].width = papers[i - 1].height; // 短边为长边
papers[i].height = papers[i - 1].width / 2; // 长边为短边的一半
}
}
// 根据纸张名称查找并打印尺寸
void printPaperSize(const char *paperName, struct Paper papers[]) {
int index = paperName[1] - '0'; // 获取纸张等级数字（如：A2 -> 2）
if (index >= 0 && index <= 9) {
printf("%s: %d mm × %d mm\n", paperName, papers[index].width, papers[index].height);
} else {
printf("无效的纸张名称。\n");
}
}
int main() {
struct Paper papers[10]; // 存储 A0 到 A9 尺寸
initializePapers(papers); // 初始化纸张尺寸
char paperName[3]; // 用于接收纸张名称（如 "A0"）
// 输入纸张名称
printf("请输入纸张名称 (A0, A1, A2, ..., A9): ");
fgets(paperName, sizeof(paperName), stdin);
// 去掉换行符
size_t len = strlen(paperName);
if (len > 0 && paperName[len - 1] == '\n') {
paperName[len - 1] = '\0';
}
// 打印相应纸张的尺寸
printPaperSize(paperName, papers);
return 0;
}
思路:
1.纸张结构体：
定义了 struct Paper 用于存储纸张的宽度和高度。
2.初始化纸张尺寸：
initializePapers(struct Paper papers[]) 函数用于初始化 A0 到 A9 的尺寸。
3.打印纸张尺寸：
printPaperSize(const char *paperName, struct Paper papers[]) 函数根据输入的纸张名称找到相应的尺寸并打印。
4.主函数：
在 main() 函数中，首先调用 initializePapers 函数来初始化纸张尺寸。
然后接收用户输入的纸张名称，并去掉换行符。
5.最后调用 printPaperSize 函数打印相应纸张的尺寸。
2.给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.
答案：
输入:
请输入你整数个数:4
请输入整数个数:1 3 6 9 6
输出
sum=117
代码：
#include "stdio.h"
#define MAX_SIZE 100 // 定义数组的最大大小
main(){
int number,num1[]={},num2[]={},i,sum=0;
printf("请输入你整数个数:");
scanf("%d",&number);
if (number > MAX_SIZE) {
printf("输入的数字超过最大限制。\n");
}
printf("请输入整数个数:");
for(i=0;i<number;i++){
scanf("%d ",&num1[i]);
num2[i] = num1[i];
}
printf("\n");
for(i=0;i<number;i++){
printf("num1 = %d num2 = %d \n",num1[i],num2[i]);
}
int j;
for(i=0;i<number;i++)
for(j=i+1;j<number;j++){
sum = sum+ num1[i] * num2[j];
}
printf("sum = %d",sum);
}
思路:
1.两两相乘的重要性
2.如何构建这个乘法
3.加起来即可以
4.通关
3、给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。
答案:
Query [0, 2]: True
Query [1, 3]: False
Query [2, 4]: False
代码:
#include <stdio.h>
#include <stdlib.h>
// 定义哈希表结构
typedef struct HashTable {
int *keys; // 键数组
int *values; // 值数组
int size; // 当前大小
int capacity; // 容量
} HashTable;
// 初始化哈希表
HashTable* createHashTable(int capacity) {
HashTable *table = (HashTable*)malloc(sizeof(HashTable)); // 分配哈希表内存
table->keys = (int*)malloc(capacity * sizeof(int)); // 分配键数组内存
table->values = (int*)malloc(capacity * sizeof(int)); // 分配值数组内存
table->size = 0; // 初始大小为0
table->capacity = capacity; // 设置容量
return table; // 返回哈希表指针
}
// 哈希函数
int hashFunction(int key, int capacity) {
return key % capacity; // 简单的取模哈希函数
}
// 插入键值对
void insert(HashTable *table, int key, int value) {
int index = hashFunction(key, table->capacity); // 计算哈希索引
table->keys[index] = key; // 插入键
table->values[index] = value; // 插入值
table->size++; // 增加大小
}
// 查找键
int find(HashTable *table, int key) {
int index = hashFunction(key, table->capacity); // 计算哈希索引
if (table->keys[index] == key) { // 如果找到键
return table->values[index]; // 返回值
}
return -1; // 未找到返回-1
}
// 预处理数列
HashTable* preprocess(int *A, int n) {
int i;
HashTable *table = createHashTable(n); // 创建哈希表
for ( i = 0; i < n; i++) { // 遍历数列
insert(table, A[i], i); // 插入键值对
}
return table; // 返回哈希表
}
// 查询处理
int canFindXorPair(int *A, int n, int x, int l, int r, HashTable *table) {
int i;
for ( i = l; i <= r; i++) { // 遍历查询区间
int target = A[i] ^ x; // 计算目标值
int pos = find(table, target); // 查找目标值
if (pos != -1 && pos >= l && pos <= r && pos != i) { // 如果找到目标值并且在区间内且不是当前位置
return 1; // 返回True
}
}
return 0; // 返回False
}
int main() {
int A[] = {3, 5, 7, 9, 11}; // 定义数列
int n = sizeof(A) / sizeof(A[0]); // 计算数列长度
int x = 6; // 定义非负整数x
int queries[][2] = {{0, 2}, {1, 3}, {2, 4}}; // 定义查询区间
int m = sizeof(queries) / sizeof(queries[0]); // 计算查询数量
int i;
HashTable *table = preprocess(A, n); // 预处理数列
for ( i = 0; i < m; i++) { // 遍历查询
int l = queries[i][0]; // 查询区间左端点
int r = queries[i][1]; // 查询区间右端点
int result = canFindXorPair(A, n, x, l, r, table); // 处理查询
printf("Query [%d, %d]: %s\n", l, r, result ? "True" : "False"); // 输出结果
}
free(table->keys); // 释放键数组内存
free(table->values); // 释放值数组内存
free(table); // 释放哈希表内存
return 0; // 返回0表示程序正常结束
}
思路:
头文件包含：
#include <stdio.h>：包含标准输入输出头文件。
#include <stdlib.h>：包含标准库头文件，用于内存分配等。
哈希表结构：
typedef struct HashTable：定义哈希表结构，包含键数组、值数组、大小和容量。
哈希表操作：
createHashTable：初始化哈希表，分配内存并设置初始值。
hashFunction：简单的取模哈希函数。
insert：插入键值对到哈希表。
find：查找键在哈希表中的值。
预处理数列：
preprocess：创建哈希表并插入数列中的每个元素及其位置。
查询处理：
canFindXorPair：处理每个查询区间
[l,r]
[l,r]，检查是否存在两个数使得它们的异或等于 x
主函数：
定义数列和查询区间。
预处理数列。
处理每个查询并输出结果。
释放分配的内存。
结尾
Come on!