C语言完毕八个递减数列中搜寻某二个数

本文实例讲述了C语言实现两个递减数列中寻找某一个数的方法,分享给大家供大家参考之用。具体方法如下:

**C语言中的数组索引必须保证位于合法的范围内!

MS100 [046]

通常来说这道题算二分查找法中非常有难度的一题了。

**示例代码如下:

括号排列数

题目如下:

enum {TABLESIZE = 100};
int *table = NULL;
int insert_in_table(int pos, int value) {
  if(!table) {
    table = (int *)malloc(sizeof(int) *TABLESIZE);
  }
  if(pos >= TABLESIZE) {
    return -1;
  }
  table[pos] = value;
  return 0;
}

四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

一个数组是由一个递减数列左移若干位形成,比如{4, 3, 2, 1, 6, 5}是由{6, 5,
4, 3, 2, 1}左移两位,在这种数组中查找某一个数。

其中:pos为int类型,可能为负数,这会导致在数组所引用的内存边界之外进行写入

思路:12种

实现代码如下:

解决方案如下:

MS100 [047]

int array[] = {4, 3, 2, 1, 6, 5};
const int size = sizeof array / sizeof *array;

int findMinNumber(int (&array)[size], int start, int last, int dest)
{
 int mid = (last - start) / 2 + start;
 int result;

 if(start > last) {
 return -1;
 }

 if(array[mid] == dest) {
 result = mid;
 return result;
 } 

 if(array[mid] <= array[start]) {
 if(dest > array[mid] && dest <= array[start]) {
 last = mid - 1;
 result = findMinNumber(array, start, last, dest);
 }
 else {
 start = mid + 1;
 result = findMinNumber(array, start, last, dest);
 }
 } else if(array[mid] > array[start]) {
 if(dest < array[mid] && dest >= array[last]) {
 start = mid + 1;
 result = findMinNumber(array, start, last, dest);
 }
 else {
 last = mid - 1;
 result = findMinNumber(array, start, last, dest);
 }
 }

 return result;
}
enum {TABLESIZE = 100};
int *table = NULL;
int insert_in_table(size_t pos, int value) {
  if(!table) {
    table = (int *)malloc(sizeof(int) *TABLESIZE);
  }
  if(pos >= TABLESIZE) {
    return -1;
  }
  table[pos] = value;
  return 0;
}

最长递减子序列

程序运行结果如下图所示:

您可能感兴趣的文章:

  • C语言柔性数组实例详解
  • C语言构建动态数组完整实例
  • C语言安全之数组长度与指针实例解析
  • C语言安全编码数组记法的一致性
  • c语言动态数组示例
  • c语言合并两个已排序数组的示例(c语言数组排序)
  • 约瑟夫环问题(数组法)c语言实现
  • C语言二维数组的处理实例
  • 深入理解c语言数组
  • C语言小程序
    数组操作示例代码
  • C语言中全局数组和局部数组的问题
  • C语言求连续最大子数组和的方法

求一个数组的最长递减子序列比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}

澳门金沙vip 1

思路:经典动态规划,方案一,记录max[i]为以a[i]接尾的最长递减子序列长度,从0到n-1不断更新max数组即可。O(n^2)

希望本文所述对大家C程序算法设计的学习有所帮助。

方案二,使用数组b[t]表示长度为t的递减子序列的末尾值的最大值,显然b[t]数组单调递减(初始化为最小值)。每次二分查找b数组,找t使b[t-1]
> a[i] && b[t] <= a[i],更新b[t] =
a[i]。最大的有效t值即为所求。恢复结果时,先找到b[t],然后从后往前扫描数组a。O(n*logn)

您可能感兴趣的文章:

  • c语言的cps实现求fibonacci数列示例
  • C语言柔性数组实例详解
  • C语言构建动态数组完整实例
  • C语言安全之数组长度与指针实例解析
  • C语言安全编码数组记法的一致性
  • C语言安全编码之数组索引位的合法范围
  • c语言动态数组示例
  • 澳门金沙vip,约瑟夫环问题(数组法)c语言实现
  • C语言二维数组的处理实例
  • 深入理解c语言数组
  • C语言数组指针的小例子
  • c语言中用字符串数组显示菜单的解决方法
  • C语言中全局数组和局部数组的问题

MS100 [048]

部分有序数组查找

微软:
一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}
是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。

思路:数组的一半是有序的,那么可以通过判断key是否在有序的一半中来决定递归的子问题。

如果a[mid]
<= a[0]
:那么a[0…mid]是纯递减数组;可以简单比较出key是否在a[0..mid]中,如果在那么问题就是标准的二分查找了;否则,a[mid+1…n-1]就是原问题的子问题了。

MS100 [053]