注册 登录
编程论坛 C语言论坛

等差数列的子序列个数, 求指导算法

东南风 发布于 2021-06-06 21:13, 2318 次点击
自已写了一个,不知对不对. 用较小的数列测试是正确的.
程序代码:
#include <stdio.h>
int adj(int *,int);
void print(int ,int ,int ,int *);
int main(void)
{
    int ar[]={2, 4, 6, 8, 10, 12};
    int len=sizeof(ar)/sizeof(ar[0]);
    printf("子序列数 = %d", adj(ar,len));
}
int adj(int *ar,int len)
{   
    int n=0;
    for (int i=2;i<len;i++)
        for (int j=0;j<=i-2;j++)
            for (int d=1;d<=(i-j)/2;d++)               
                if ((i-j) % d == 0){   
                    ++n;
                    print(i,j,d,ar);
                }
    return n;                  
}
void print(int i,int j,int d,int *ar)
{
    for (;j<=i;j+=d)
        printf("%d ", ar[j]);
    putchar('\n');
}
4 回复
#2
纯蓝之刃2021-06-07 08:57
你这个只要整个数组为等差数列时正确,如果数组不为等差数列,得到的值不对。

程序代码:
#include <stdio.h>

int adj(int *,int);
void print(int,int *);

int main(void)
{
    int ar[]= {2, 4, 6, 8, 10, 12};
    int len=sizeof(ar)/sizeof(ar[0]);
    printf("子序列数 = %d", adj(ar,len));
}

int adj(int *ar,int len)
{
    int n=0,j,k,step_len,diff=0;
    for (step_len=3; step_len<=len; step_len++)
    {
        for (j=0; j<=len-step_len; j++)
        {
            for (k=j; k<j+step_len-1; k++)
            {
                if(k==j)
                    diff=ar[k+1]-ar[k];

                //printf("j=%d,k=%d,ar[k]=%d,ar[k+1]=%d,diff=%d\n",j,k,ar[k],ar[k+1],diff);

                if(ar[k+1]-ar[k] != diff)
                    break;
            }
            if(k==j+step_len-1)
            {
                ++n;
                print(step_len,ar+j);
            }
        }
    }
    return n;
}

void print(int j,int *ar)
{
    int n=0;
    while(n<j)
        printf("%d ", ar[n++]);
    putchar('\n');
}
#3
东南风2021-06-07 10:28
回复 2楼 纯蓝之刃
谢谢, 老师指点. 您代码中语句: diff=ar[k+1]-ar[k] 意味着只能找到公差为两相邻元素之差的子序列. 比如例子中还有"2 6 10"和"4 8 12"没有找到. 对大师代码还没有完全看懂, 请大师再核实一下代码.
#4
rjsp2021-06-07 10:36
把完整的题目要求发一下
#5
东南风2021-06-07 11:34
回复 4楼 rjsp
一个人在VBA论坛上问的, 是力扣上的一个题目:https://
1