首页 > 试题广场 >

Kolakoski 序列

[编程题]Kolakoski 序列
  • 热度指数:1259 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
Kolakoski 序列是个自生成的无限序列。
例如,当给定的整数组为 [1, 2] 时,Kolakoski 序列是这样的:
    [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…]
如果我们将相邻的相同的数字分成一组,那么将会得到:
    [[1],[2,2],[1,1],[2],[1],[2,2],[1],[2,2],[1,1],[2],[1,1],[2,2],[1],[2],[1,1],[2],[1],[2,2],[1,1],…]
可以看出,每组数字交替由 1, 2 组成。
接下来对每个分组求他的长度,得到:
    [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…]
可以看出,经过如上的变换后,数列保持不变。
对于其他给定的整数组,同样可以用类似的方法构造 Kolakoski 序列,例如给定整数组 [2, 3] 时:
    [2,2,3,3,2,2,2,3,3,3,2,2,3,3,2,2,3,3,3,2,2,2,3,3,3,2,2,3,3,…]
给定整数组 [2, 1, 3, 1] 时,构造得到如下:
    [2,2,1,1,3,1,2,2,2,1,3,3,1,1,2,2,1,3,3,3,1,1,1,2,1,3,3,1,1,…]

输入描述:
输入由两行组成:
第一行包括两个正整数 n, m
第二行包括 m 个正整数 a[]
数据规模与限制:
0 < n < 10000
1 < m < 1000
0 < a[i] < 1000
a[i] 不等于 a[i + 1]
a[0] 不等于 a[m-1]


输出描述:
每行一个数字,共 n 行
整数组 a 生成的 Kolakoski 序列的前 n 项
示例1

输入

30 4
2 1 3 1

输出

2
2
1
1
3
1
2
2
2
1
3
3
1
1
2
2
1
3
3
3
1
1
1
2
1
3
3
1
1
2
思路其实差不多,也是直接vector用push_back的方式去把vector<int> res按照题目规则做出来,但是本题需要考虑几个坑点。
1.首元素是1的时候,res的构造方式是不一样的,需要单独拉出来讨论
2.如果发现时间超时或者内存不够,那可能是卡在循环里了,毕竟最多才10000的数据量,不可能超时或者内存不够。
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
//数据输入
    int count, len;
    cin >> count >> len;
    int counttemp = count;
    vector<int> ivec(len);
    for (int i = 0; i < len; i++)
    {
        int temp;
        cin >> temp;
        ivec[i] = temp;
    }
//处理res开头部分
    vector<int> res;
    int index_r = 1, index_i = 1;
    for (int i = 0; i < ivec[0]; i++)
    {
        res.push_back(ivec[0]);
        if (ivec[0] == 1)
        {
            for (int j = 0; j < ivec[1]; j++)
            {
                res.push_back(ivec[1]);
            }
            index_i++;
            index_r++;
            index_i = index_i % ivec.size();
        }
    }
//继续构造res数组
    while (res.size()<count)
    {
        for (int i = 0; i < res[index_r]; i++)
        {
            res.push_back(ivec[index_i]);
        }
        index_i++;
        index_r++;
        index_i = index_i % ivec.size();
    }
//循环输出结果
    for (int i = 0; i < counttemp; i++)
    {
        cout << res[i] << endl;
    }
    return 0;
}

发表于 2019-04-29 22:51:34 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int a[m], s[n];
    for(int i=0;i<m;i++)
        scanf("%d", &a[i]);
    for(int i=0,p=0,k=0;i<n;p++){
        if(i == p)
            s[p] = a[k];
        for(int j=0;j<s[p] && i<n;j++){
            printf("%d\n", a[k]);
            s[i++] = a[k];
        }
        k = (k+1)%m;
    }
    return 0;
}

发表于 2020-11-21 01:06:13 回复(0)
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> nums(m);
    for (int i = 0; i < m; i++) {
        cin >> nums[i];
    }

    vector<int> ko(n);

    int j = 0; // a的下标
    int i = 0; //ko最大下标
    int k = 0; //ko的下标


    while (i < n) {

        if (i > k) {
            for (int x = 0; x < ko[k] && i < n; x++) {
                ko[i] = nums[j % m];
                i++;
            }
        } else {
            for (int x = 0; x < nums[j % m] && i < n; x++) {
                ko[i] = nums[j % m];
                i++;
            }
        }

        j = (j + 1) % m;
        k++;
    }

    for (int x = 0; x < n; x++) {
        cout << ko[x] << endl;
    }
}
// 64 位输出请用 printf("%lld")
发表于 2024-01-17 13:25:14 回复(0)
// 暴力模拟
#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> num(m);
    vector<int> ans;
    for(int i = 0; i < m; ++i)
        cin >> num[i];
    int i = 0,j = 0, count = 0,temp = num[0];
    while(count < n)
    {
        while(temp--)
        {
            ans.push_back(num[i]);
            count++;
            if(n == count)
                break;
        }
        i++;
        i %= num.size();
        j++;
        temp = (ans.size() < 2 ? num[1]:ans[j]);
    }
    for(int i = 0; i < ans.size() ;++i)
        cout << ans[i] << endl;
    return 0;
}

编辑于 2019-05-16 20:53:22 回复(0)
import sys
n, m = [int(num) for num in sys.stdin.readline().split(" ")]
a = [int(num) for num in sys.stdin.readline().split(" ")]
if len(a) == 0:    
    print()
    sys.exit()
res = [a[0] for _ in range(a[0])]
if a[0] != 1:
    ai = 1 % len(a)
    i, j = 1, a[0]
else:
    res += [a[1] for _ in range(a[1])]
    ai = 2 % (len(a))
    i, j = 2, a[0] + a[1]
while j < n:
    res += [a[ai] for _ in range(res[i])]
    j += res[i]
    i += 1
    ai = (ai + 1) % len(a)
for num in res[:n]:
    print(num)

发表于 2019-03-31 11:15:00 回复(0)

第一个测试,应该输出999,我的输出也是999
但是就是说通不过:
题目说明里面给的例子也能通过

代码如下:
n,m=[int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
res = []
for i in range(a[0]):
    res.append(a[0])
if a[0]==1:
    for i in range(a[1]):
        res.append(a[1])
    index=2
else:index =1
while len(res)<n:
    times = res[index]
    # print("index:",index,"to add:",a[index%m],"times:",times)
    for i in range(times):
          res.append(a[index%m])
    # print("res:",res)
    index+=1
for i in res:
    print(i)

发表于 2019-03-21 11:44:56 回复(2)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);
        strs = br.readLine().split(" ");
        int[] arr = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            arr[i] = Integer.parseInt(strs[i]);
        }

        for (Integer e : genKolakoski(arr, n, m)) {
            System.out.println(e);
        }
    }

    private static ArrayList<Integer> genKolakoski(int[] a, int n, int m) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int p = 0, q = 0; n > 0; p++, q++) {
            if (p == m) p = 0;
            res.add(a[p]);
            n--;

            for (int i = 0; i < res.get(q) - 1 && n > 0; i++) {
                res.add(a[p]);
                n--;
            }
        }
        return res;
    }
}

发表于 2019-03-11 17:10:54 回复(0)
暴力破解

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
    int i, j, k, n, m, input;
    vector <int> base, kolakoski;
    
    cin >> n >> m;
    for(i = 0; i < m; i++)
    {
        cin >> input;
        base.push_back(input);
    }
    
    for(i = 0; i < base[0]; i++)
    {
        kolakoski.push_back(base[0]);
    }
    i = j = 1;
    while(kolakoski.size() < n)
    {
        if(j >= kolakoski.size()) //考虑到第一个元素是1的情况
        {
            for(k = 0; k < base[i]; k++)
            {
                kolakoski.push_back(base[i]);
            }
            j++;
            i = (i + 1) % m;
        }
        else
        {
            for(k = 0; k < kolakoski[j]; k++)
            {
                kolakoski.push_back(base[i]);
            }
            i = (i + 1) % m;
            j++;
        }
    }
    
    for(i = 0; i < n; i++)
    {
        cout << kolakoski[i] <<endl;
    }
    
    return 0;
}

发表于 2019-01-28 11:56:09 回复(0)
暴力模拟
#include<iostream>
using namespace std;
const int maxn = 10001;
const int maxm = 1001;
intmain()
{
    int n, m;
    int r = 0, l = 0, k = 0;
    int a[maxm], b[maxn];
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>a[i];
    while(r < n)
    {
        if(b[l] == 0) b[l] = a[k];
        for(int i=0;i<b[l];i++)
        {
            b[r+i] = a[k];
        }
        k++;
        k = k % m;
        r = r + b[l];
        l++;       
    }
    for(int i=0;i<n;i++) cout<<b[i]<<endl;
    return 0;
}
编辑于 2018-09-15 10:47:54 回复(0)
主要就是在两个数组之间取下一次打印若干相同数字的次数
import java.util.Scanner;


public class Main
{          public static void main(String[] args)     {         Scanner sc = new Scanner(System.in);         int outNum = sc.nextInt();//输出长度         int len = sc.nextInt();//个数         int[] arr = new int[len];//组成数组         for(int i=0;i<len;i++)         {             arr[i] =sc.nextInt();         }         int p1=0;//组成数字的位置         int p2=0;//输出数组的位置         int[] out = new int[outNum];         int num = 0;//一个数字输出的次数                  while(true)         {             if(num>=outNum)                 break;             int times = num==0?arr[p1]:out[num];//第一次使用第一个数字作为次数             if(times==0)//如果输出数组已经无法再遍历,那么就要从存数的数组再找数字             {                 times=arr[p1];             }             num++;             for(int i=0;i<times;i++)//取一个位置的值n,赋n个n             {                 if(p2>=outNum)                     break;                 out[p2] = arr[p1];                 p2++;             }             p1 = (p1+1)%len;//p1右移                                       if(p2>=outNum)                 break;         }                  for(int i=0;i<outNum;i++)         {             System.out.println(out[i]);         }         sc.close();     }

}

发表于 2018-05-23 22:49:15 回复(0)