帮忙写个算法：两个递增数列排序后求第n个数

Question

已知数A和数B，且A>B
数列一：第一个数为1/(A+B)，增量为2/(A+B)，往下递增，即1/(A+B)、3/(A+B)、5/(A+B)……
数列二：第一个数为1/(A-B)，增量为2/(A-B)，往下递增，即1/(A-B)、3/(A-B)、5/(A-B)……
两个数列放到一起排序，求排序后的第n个数是多少？

Answer 1

为了不出现除不尽的数，把数列的所有数放大(A+B)(A-B)倍，则有以下两个数列：
数列一：(A-B)、3(A-B)、5(A-B)、7(A-B)、9(A-B)、……
数列二：(A+B)、3(A+B)、5(A+B)、7(A+B)、9(A+B)、……
比如A=4，B=1：
3、5、9、15、21、25、……

Answer 2

 decimal A = 50;
            decimal B = 15;            arryA = new ArrayList();
            ArrayList arryB = new ArrayList();
            bool flag = false;            for (int i = 1; i <= 100; i = i + 2)
            {
                arryA.Add(i / (A + B));
                arryB.Add(i / (A - B));            
            }            for (int i = 0; i < arryB.Count; i++)
            {
                for (int j = i; j < arryA.Count; j++)
                {
                    if (!flag)
                    {
                        if (Convert.ToDecimal(arryB[i]) - Convert.ToDecimal(arryA[j]) > 0)
                        {
                            arryA.Insert(j, arryB[i]);
                            flag = true;
                        }
                    }
                }
            }
            for (int i = 0; i < arryA.Count; i++)
            {
                Console.WriteLine(arryA[i]);
            }

Answer 3

这是一个线性的关系，求出数列1插入数列2的“插入步长”就可以了，这个步长应该是：step=B%(A-B)+1也就是插了“step”个数列1之后插一个数列2，又插“step”个数列1跟一个数列2……代码就不写了。

Answer 4

sorry
个数不一样 

Answer 5

decimal A = 50; 
            decimal B = 15;             arryA = new ArrayList(); 
            ArrayList arryB = new ArrayList(); 
            bool flag = false;             for (int i = 1; i <= 100; i = i + 2) 
            { 
                arryA.Add(i / (A + B)); 
                arryB.Add(i / (A - B));            
            }             for (int i = 0; i < arryB.Count; … 

Answer 6

不知道是不是这个意思,止戈老大看看:                decimal A = 4;
                decimal B = 1;                int IndexA = 1;
                int IndexB = 1;
                
                ArrayList arry = new ArrayList();                int FindIndex = 3;
                int n = 0;                while (n < FindIndex)
                {
                    if (IndexA * (A + B) < IndexB * (A - B))
                    {
                        arry.Add(IndexA * (A + B));
                        IndexA = IndexA + 2;
                    }
                    else
                    {
                        arry.Add(IndexB * (A - B));
                        IndexB = IndexB + 2;
                    }
                    n++;
                }                Console.Write(decimal.Parse(arry[FindIndex - 1].ToString()) / ((A - B) * (A + B)));
                Console.ReadLine();

Answer 7

补充了下:                decimal A = 4;
                decimal B = 1;                int IndexA = 1;
                int IndexB = 1;
                
                ArrayList arry = new ArrayList();                int FindIndex = 3;  //这里是要找到的N
                int n = 0;
                
                while (n < FindIndex)
                {
                    //两组数都扩大了(A+B)(A-B)
                    //相同就有先排A的
                    if (IndexA * (A + B) <= IndexB * (A - B))
                    {
                        arry.Add(IndexA * (A + B));
                        IndexA = IndexA + 2;
                    }
                    else
                    {
                        arry.Add(IndexB * (A - B));
                        IndexB = IndexB + 2;
                    }
                    n++;
                }                //输出时两组数都除(A+B)(A-B)
                Console.Write(decimal.Parse(arry[FindIndex - 1].ToString()) / ((A - B) * (A + B)));                Console.ReadLine();
       

Answer 8

double A = Convert.ToDouble(this.textBox1.Text); //输入A数的值
            double B = Convert.ToDouble(this.textBox2.Text); //输入B数的值
            int N = Convert.ToInt32(this.textBox3.Text); //要求的N个数
            List<double> list=new List<double>();            double tempAdd = 0;
            double tempSub = 0;            for (int i = 1, j = 0; j < N; i = i + 2, j++)
            {
                tempAdd = i / (A + B);
                tempSub = i / (A - B);
                list.Add(tempAdd);
                list.Add(tempSub);
            }            list.Sort(); //从低道高排序            this.textBox4.Text = list[N].ToString(); //输出结果

Answer 9

我的算法不是很优化。 既然要求第N个数那么产生的数列中最多全在某个数列中（当然这不太可能），极端情况下 全在第一个或第二个数列中，
所以让第一个和第二个分别数列产生N个值，组合后排序，得到第N个值，有点像穷举，可以优化下，你说的排序后只能是从小到大，如果从大到小那就没办法了，

Answer 10

哦,数相同是当作一个哦.再改下就好了。                decimal A = 40;
                decimal B = 10;                int IndexA = 1;
                int IndexB = 1;
                
                ArrayList arry = new ArrayList();                int FindIndex = 4;  //这里是要找到的N
                int n = 0;
                
                while (n < FindIndex)
                {
                    //两组数都扩大了(A+B)(A-B)
                    //相同就有先排A的
                    if (IndexA * (A + B) < IndexB * (A - B))
                    {
                        arry.Add(IndexA * (A + B));
                        IndexA = IndexA + 2;
                    }
                    else if (IndexB * (A - B) < IndexA * (A + B))
                    {
                        arry.Add(IndexB * (A - B));
                        IndexB = IndexB + 2;
                    }
                    else
                    {
                        arry.Add(IndexA * (A + B));
                        IndexA = IndexA + 2;
                        IndexB = IndexB + 2;
                        FindIndex--;   //有数相同，就往前一个
                    }
                    n++;
                }                //输出时两组数都除(A+B)(A-B)
                Console.Write(decimal.Parse(arry[FindIndex - 1].ToString()) / ((A - B) * (A + B)));                Console.ReadLine();

Answer 11

既然是线性的，出现相同情况的步长也是一样的（也可能没有相同的），再把这个步长求出来，加上前面的“插入步长”，就可以求出 N 位置是什么数了。
当然，用迭代也是一种方法。但是这种纯数学的问题，最好还是归纳公式好点。
用迭代的话用泛型List<>吧。

Answer 12

为什么非要用数组？
不用数组的效率更高，空间更低。
代码如下using System;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("A=4 B=1");
            for(int i = 1;i < 20;i++)
                Console.Write(Get(4, 1, i).ToString() + " ");
            Console.WriteLine();
            Console.WriteLine("A=6 B=2");
            for(int i = 1;i < 20;i++)
                Console.Write(Get(6, 2, i).ToString() + " ");
            Console.WriteLine();
        }
        static int Get(int A, int B, int N)
        {
            int a = A - B;
            int b = A + B;
            int t, w, q, p;
            if(a > b)
            {
                t = a;
                a = b;
                b = t;
            }
            p = a;
            q = b;
            w = 1;
            while(w < N)
            {
                if(p + a * 2 < q)
                {
                    p += a * 2;
                    w++;
                }
                else if(p == q)
                {
                    p += a * 2;
                    q += b * 2;
                    w++;
                }
                else
                {
                    p += a * 2;
                    q += b * 2;
                    w += 2;
                }
            }
            if(w == N)
                return (p);
            else
                return (q - b * 2);
        }
    }
}
/*
A=4 B=1
3 5 9 15 15 21 25 27 33 35 39 45 45 51 55 57 63 65 69
A=6 B=2
4 8 12 20 24 28 36 40 44 52 56 60 68 72 76 84 88 92 100
*/

Answer 13

                decimal A = 40;
                decimal B = 10;                int IndexA = 1;
                int IndexB = 1;                ArrayList arry = new ArrayList();                int FindIndex = 1;  //这里是要找到的N
                int n = 0;
                int SameCount = 0;                while (n < FindIndex)
                {
                    //两组数都扩大了(A+B)(A-B)
                    //相同就有先排A的
                    if (IndexA * (A + B) < IndexB * (A - B))
                    {
                        arry.Add(IndexA * (A + B));
                        IndexA = IndexA + 2;
                    }
                    else if (IndexB * (A - B) < IndexA * (A + B))
                    {
                        arry.Add(IndexB * (A - B));
                        IndexB = IndexB + 2;
                    }
                    else
                    {
                        arry.Add(IndexA * (A + B));
                        IndexA = IndexA + 2;
                        IndexB = IndexB + 2;                        
                    }                    n++;
                }                //输出时两组数都除(A+B)(A-B)
                Console.Write(decimal.Parse(arry[FindIndex - 1].ToString()) / ((A - B) * (A + B)));                Console.ReadLine();

Answer 14

呵呵 ，求N个数，如果N偶数，一次插两个数 ，N/2次就可以求到，而且本身冒个泡就成，而且对于同一步长来说
1/(A+B) 永远小于1/(A-B),so，对于N为偶数来说就是 (1+（N/2）*2)/(A-B)而N位奇数，就比较一下 （N+1)/2处的 1/(A+B)和前面那一项的大小就成

Answer 15

之前想了一阵子，觉得头脑有些混乱，干脆上来CSDN问问。
实际就是要把公式推出来。。

Answer 16

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace MyGet
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("请您输入Ａ的值：");
            double A = Convert.ToDouble(Console.ReadLine());
            Console.WriteLine("请您输入Ｂ的值：");
            double B = Convert.ToDouble(Console.ReadLine());
            Console.WriteLine("请您输入您要值的序列：");
            int Count = Convert.ToInt32(Console.ReadLine());
            Queue Alist = new Queue();
            Queue Blist = new Queue();
            ArrayList TarList = new ArrayList();
            for (int i = 0; i < Count; i++)
            {
                Alist.Enqueue((2 * i + 1) / (A + B));
                Blist.Enqueue((2 * i + 1) / (A - B));
            }
            while (Alist.Count > 0 && Blist.Count > 0)
            {
                double TempA = Convert.ToDouble(Alist.Peek());
                double TempB = Convert.ToDouble(Blist.Peek());
                if (TempA < TempB)
                {
                    TarList.Add(TempA);
                    Alist.Dequeue();
                }
                else
                {
                    TarList.Add(TempB);
                    Blist.Dequeue();
                }
            }
            while (Alist.Count > 0)
            {
                TarList.Add(Alist.Dequeue());
            }
            while (Blist.Count > 0)
            {
                TarList.Add(Blist.Dequeue());
            }
            Console.WriteLine("您要取回的值为："+TarList[Count]);
         
        }
    }
}

Answer 17

应该有更高效的方法数列一：第一个数为1/(A+B)，增量为2/(A+B)，往下递增，即1/(A+B)、3/(A+B)、5/(A+B)
数列二：第一个数为1/(A-B)，增量为2/(A-B)，往下递增，即1/(A-B)、3/(A-B)、5/(A-B)将2个数列都乘以A^2 - B^2 =>数列一：第一个数为1*(A-B)，增量为2*(A-B)，往下递增，即1*(A-B)、3*(A-B)、5*(A-B)
数列二：第一个数为1*(A+B)，增量为2*(A+B)，往下递增，即1*(A-B)、3*(A+B)、5*(A+B)求一下A+B与A-B的最大公约数M,应该可以计算出循环节的长度L, L = (A+B)/M + (A-B)/M - 1
用N/L可以计算出需要删掉多少个数,这样基本上用常数时间就可以求出来了,不用循环!整个算法效率最低的地方可能就是用辗转相除求最大公约数,印象里平均复杂度好像是ln(n),

Answer 18

有兴趣的朋友请继续讨论，我会另外开帖给分。为了不出现除不尽的数，把数列的所有数放大(A+B)(A-B)倍，则有以下两个数列： 
数列一：(A-B)、3(A-B)、5(A-B)、7(A-B)、9(A-B)、…… 
数列二：(A+B)、3(A+B)、5(A+B)、7(A+B)、9(A+B)、…… 我的思路是：
(A+B)和(A-B)的最小公倍数将是共同的数，那么n倍最小公倍数也将是两个数列共同的数。

Answer 19

到下面这个帖子留个名，以便到时结帖给分，谢谢。
http://topic.csdn.net/u/20090223/11/2de7a6f3-d1d7-47ac-af0b-757b99e39927.html

Answer 20

long n_value=n*(A-B);
for(int i=1;i<=n;i++)
{
  
  if(i*(A+B)>n_value)return n_value/(A-B)/(A+B);
  if(i*(A+B)>n_value-2*(A-B))return i/(A-B);
  n_value-=2*(A-B);
}

Answer 21

把两列数组都乘以(a-b), 那么一列就变成是1,3,5...（我们称它为A），另一列就是1*(a-b)/(a+b), 3*(a-b)/(a+b),...(B)，合并后的数组为C
我们知道给定n, B(n) 的给定 一定比 A(n) 要小，但是 C(n) 至少比 B(n) 大。C(n) <= B(n) < A(n)
我们要求C(n), 但是我们很容易找到B(n)=(2n-1)*(a-b)/(a+b),(n = 1, 2, 3..)。
然后，我们知道A里面都是整数(1,3,5,7,..)，那么，我们通过对B(n)取整数，看距离这个整数最近的奇数是几，就知道B(n)后面包含了多少A的元素。
至于A,B重复的元素，只要看看能够使得k*(a-b)/(a+b)为整数的最小k是几，然后任何k的倍数都是了。

Answer 22

已知数A和数B，且A>B
数列一：第一个数为1/(A+B)，增量为2/(A+B)，往下递增，即1/(A+B)、3/(A+B)、5/(A+B)……
数列二：第一个数为1/(A-B)，增量为2/(A-B)，往下递增，即1/(A-B)、3/(A-B)、5/(A-B)……
两个数列放到一起排序，求排序后的第n个数是多少？两数列放大 (A+B)(A-B)
数列1 为an = (2n+1)(A-B)  n= 0,1,2,3.....
数列2 为bn = (2n+1)(A+B) n= 0,1,2,3...前提A != B 
设ai = bk;
(2i+1)(A-B) = (2k+1)(A+B)
2(i-k)A = 2(i+k+1)B      (*)假设第n个数为anan 的ai在合并数列的下标为 [i + k+1](取整)  
设第n个数为ai
即
i+k+1 = n-1               (1)i-k = (n-1)B/A            (2)
(1)和(2) 联合得
i = F(n)                  (3)
//修正: 如果(*) 关于i,k 有整数解时,且bn优先排序在an时修正为F(n)+1,其他情况不变同样
设第n个数为bk
bk 的在合并数列的位置为 [k + i+1](取整) 
k+i+1 = n-1
i-k = (n-1)B/A k = G(n)                   (4)
//修正: 如果(*) 关于i,k 有整数解时,且an优先排序在bn时修正为G(n)+1,其他情况不变程序应该在常数时间内结束

Answer 23

大家看看我的，楼主也看过来#include <iostream.h>#define A 3
#define B 1float an(int n)
{
    return (2*n-1.0) / (A+B);
}float bn(int n)
{
    return (2*n-1.0) / (A-B);
}float cn(int n)
{
    int x = 0;
    int y = 0;    while( (x+y) < n )
    {
        y++;        int tmp = (A+B)*y - B;        if( (tmp%(A-B)) == 0 )
        {
            x = tmp / (A-B);
        }
        else
        {
            x = tmp/(A-B) + 1;
        }        x--;
    }    if( (x+y) == n )
    {
        return bn(y);
    }
    else
    {
        y--;        return an(n-y);
    }
}void main()
{
    cout<<"an:"<<endl;
    for(int i=1; i<=20; i++)
    {
        cout<<an(i)<<" ";
    }
    cout<<endl;    cout<<"bn:"<<endl;
    for(int i=1; i<=20; i++)
    {
        cout<<bn(i)<<" ";
    }
    cout<<endl;    cout<<"cn:"<<endl;
    for(int i=1; i<=20; i++)
    {
        cout<<cn(i)<<" ";
    }
    cout<<endl;}

Answer 24

帮忙看看我的问题
http://topic.csdn.net/u/20090724/17/90f076b3-8948-4cea-83e3-78dc96146103.html?seed=1804070590&r=58604121#r_58604121

Answer 25

俺是新人，不过还是有个想法求指正：可以只保存n<=lcm(A+B, A-B)的结果， 其中lcm为最小公倍数
当n>lcm(A+B, A-B)时
可以由n % lcm(A+B, A-B)的结果 加上某个常数在O(1)时间内算出来

Answer 26

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;/*已知数A和数B，且A>B
数列一：第一个数为1/(A+B)，增量为2/(A+B)，往下递增，即1/(A+B)、3/(A+B)、5/(A+B)……
数列二：第一个数为1/(A-B)，增量为2/(A-B)，往下递增，即1/(A-B)、3/(A-B)、5/(A-B)……
两个数列放到一起排序，求排序后的第n个数是多少？
*/namespace 两个数列重排序输出第n个数值
{
    class Program
    {
        static void Main(string[] args)
        {
            System.Console.WriteLine("input number A:");            int a = int.Parse(System.Console.ReadLine());            System.Console.WriteLine("input number B:");            int b = int.Parse(System.Console.ReadLine());
            double[] arr1 = new double[20];            for (int i = 0; i < arr1.Count(); i++)
            {
                arr1[i] = 1 / ((double)a + (double)b) + i * 2 / ((double)a + (double)b);
            }            double[] arr2 = new double[20];            for (int i = 0; i < arr2.Count(); i++)
            {
                arr2[i] = 1 / ((double)a - (double)b) + i * 2 / ((double)a - (double)b);
            }            double[] arrAll = new double[20];            for (int i = 0; i < arrAll.Count(); i++)
            {
                if (i < 10)
                {
                    arrAll[i] = arr1[i];
                }                else
                    arrAll[i] = arr2[i];            }
            Array.Sort(arrAll);
            System.Console.WriteLine("重排列后数组如下");            for (int i = 0; i < arrAll.Count(); i++)
            {
                System.Console.Write(arrAll[i] + " ");
            }
            System.Console.WriteLine("请输入要的第n个数");            int index = int.Parse(System.Console.ReadLine());            System.Console.WriteLine(arrAll[index - 1]);        }
    }
}新手，多多指教！

Answer 27

也就是算法问题。虽然已经结帖，我再发个不用数组的C# WinForm 的
两数列放大 (A+B)(A-B)        private void btCalc_Click(object sender, EventArgs e)
        {
            int a = Convert.ToInt32(txtA.Text);
            int b = Convert.ToInt32(txtB.Text);
            int n = Convert.ToInt32(txtn.Text);
            int c1 = a - b;
            int c2 = a + b;
            int i;
            int d1 = 1;
            int d2 = 1;
            int f1=c1;
            int f2=c2;
            int r=c1;
            txtPaixu.Text = c1.ToString();
            if (n > 1)
            {
                for (i = 2; i <= n; i++)
                {
                    if (f1 == f2)
                    {
                        d1 += 2;
                        d2 += 2;
                        f1 = c1 * d1;
                        f2 = c2 * d2;
                        r = f1;
                    }
                    else if (f1 < f2)
                    {
                        d1 += 2;
                        r = f2;
                        f1 = c1 * d1;
                    }
                    else
                    {
                        d2 += 2;
                        r = f1;
                        f2 = c2 * d2;
                    }
                    txtPaixu.Text += "," + r.ToString();
                }
            }
            txtAns.Text = r.ToString();
        }