21xrx.com
2024-11-08 20:17:17 Friday
登录
文章检索 我的文章 写文章
C++编程:求两数之和小于给定值n
2023-07-02 19:19:09 深夜i     --     --
C++ 数学 算法 运算符 循环

近年来,C++编程已经成为了计算机专业最重要的学科之一。而在C++编程中,求两数之和小于给定值n也是常见的编程问题之一。在本文中,我将介绍如何使用C++编写程序来解决这一问题。

首先,我们需要明确问题的具体要求。这个问题给定一个数组和一个目标值n,要求找出数组中所有的两个数的组合,使得这两个数之和小于n。接下来,我们可以考虑使用暴力枚举的方法来解决这个问题。

具体地说,我们可以使用双重循环遍历所有的数对,然后判断这两个数之和是否小于目标值n。如果是,就输出这两个数。代码如下:


#include <iostream>

#include <vector>

using namespace std;

vector<pair<int, int> > solve(vector<int>& nums, int target) {

  vector<pair<int, int> > res;

  for (int i = 0; i < nums.size(); i++) {

    for (int j = i + 1; j < nums.size(); j++) {

      if (nums[i] + nums[j] < target) {

        res.push_back(make_pair(nums[i], nums[j]));

      }

    }

  }

  return res;

}

int main() {

  int n, target;

  cin >> n >> target;

  vector<int> nums(n);

  for (int i = 0; i < n; i++) {

    cin >> nums[i];

  }

  vector<pair<int, int> > res = solve(nums, target);

  for (int i = 0; i < res.size(); i++) {

    cout << res[i].first << " " << res[i].second << endl;

  }

  return 0;

}

在此程序中,我们使用了C++中的vector容器来存放答案。其中,vector >表示一个由两个int类型组成的pair的动态数组,make_pair用来构造一个pair。最后我们使用循环输出所有符合要求的数对。显然,暴力枚举的时间复杂度是O(n^2),对于很大的输入数据,会非常缓慢。

接下来,我们可以考虑使用排序和双指针的方法来优化代码。我们可以对数组进行从小到大的排序,然后使用双指针来找到符合要求的数对。具体来说,我们可以让左右指针分别指向数组的第一个元素和最后一个元素,然后判断这两个数之和是否小于目标值n。如果是,就输出这两个数,并将左指针右移一位;否则,将右指针左移一位。当左指针和右指针相遇时,就结束搜索。代码如下:


#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<pair<int, int> > solve(vector<int>& nums, int target) {

  vector<pair<int, int> > res;

  sort(nums.begin(), nums.end()); // 对数组进行排序

  int left = 0, right = nums.size() - 1;

  while (left < right) { // 使用双指针

    if (nums[left] + nums[right] < target) {

      for (int i = left + 1; i <= right; i++) {

        res.push_back(make_pair(nums[left], nums[i]));

      }

      left++;

    } else

      right--;

    

  }

  return res;

}

int main() {

  int n, target;

  cin >> n >> target;

  vector<int> nums(n);

  for (int i = 0; i < n; i++) {

    cin >> nums[i];

  }

  vector<pair<int, int> > res = solve(nums, target);

  for (int i = 0; i < res.size(); i++) {

    cout << res[i].first << " " << res[i].second << endl;

  }

  return 0;

}

在此程序中,我们使用了C++中的sort函数来对数组进行排序,时间复杂度为O(nlogn)。然后我们使用双指针来遍历数组,时间复杂度为O(n)。因此,该算法的总时间复杂度为O(nlogn)。相比暴力枚举,时间复杂度得到了极大的优化,对于大规模的数据输入,应该可以快速得到答案。

总之,本文介绍了使用C++编程求两数之和小于给定值n的方法。从暴力枚举到排序和双指针,我们一步步优化算法,使得程序的执行效率得到了很大的提升。C++编程虽然有一定的难度,但随着我们的学习和实践,相信我们能够顺利掌握这门学科,为未来的计算机工作打下坚实的基础。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复